829. The Day Each Order Is Filled
A chain has n depots numbered 1 .. n. Deliveries run for m days; on day j a lorry
drops v[j] crates at EVERY depot from l[j] to r[j] inclusive. Days happen in the order
given and nothing is ever removed.
Then q standing orders are read. Order i names a depot w[i] and a quantity need[i].
Print, for each order, the earliest day by which that depot has received at least that many
crates in total, counting days from 1, or -1 if it never does.
depots 4, days (1..2 +5), (2..4 +3), (1..4 +2)
orders (depot 2, need 8) -> 2 (depot 4, need 6) -> -1 (depot 1, need 100) -> -1
## Each order alone is a binary search, and that is not enough
For one order the answer is monotone in the day: crates are only ever added, so once a depot has
enough it still has enough on every later day. So "is day t enough?" is false and then true,
and one order could be answered by a binary search over t, with each check replaying the
first t days. That costs O(m log m) per order and O(q m log m) in total, which at the
limits is far too much.
The waste is obvious once you see it: every order replays the same days from scratch.
## Parallel binary search
Run all q searches AT THE SAME TIME, one round at a time.
lo[i] = 1 and hi[i] = m + 1 for every order, where m + 1 means "never"
repeat until every lo[i] == hi[i]:
for each unfinished order i: mid[i] = lo[i] + (hi[i] - lo[i]) / 2
bucket the orders by their mid
clear the structure
replay days 1, 2, ..., m in order, and after applying day j
answer every order sitting in bucket j
One round replays the days ONCE and advances every search by one step, so the whole thing costs
log2(m + 1) rounds rather than q separate searches. This is the technique's name: parallel
binary search, or offline binary search.
The structure being replayed has to support "add v to a range" and "read one position", which
a Fenwick tree does in O(log n) if you store the DIFFERENCE array: adding v to
l .. r becomes +v at l and -v at r+1, and reading position w becomes the prefix
sum up to w.
## The invariant, per order
> the earliest sufficient day for order i, or m + 1 if there is none, lies in
> [lo[i], hi[i]].
When the replay reaches day mid[i] and the depot already has enough, set hi[i] = mid[i],
keeping mid[i] in play. Otherwise set lo[i] = mid[i] + 1.
The sentinel m + 1 is what lets the SAME loop report "never" without a special case. Note the
midpoint can never come out as m + 1 itself: with lo < hi <= m + 1 the value
lo + (hi - lo) / 2 is strictly below hi, so it is at most m and always a real day.
## Why it terminates
Each round halves hi[i] - lo[i] for every unfinished order, exactly as an ordinary binary
search does, so after ceil(log2(m + 1)) rounds every range holds one value.
## What is printed when no day is enough
lo[i] ends at m + 1, and that is reported as -1. The case is real: the second order
above asks for 6 crates at depot 4, which only ever receives 5.
## Overflow
A depot can receive m deliveries of 10^9 crates, which is 2 * 10^13, and need reaches
10^14. Both need 64 bits. Both also stay inside the exact-integer range of a JavaScript
number, which ends just above 9 * 10^15.
## Cost
Time O((m + q) log n log m). Space O(n + m + q).
Constraints - `1 ≤ n ≤ 20000` - `1 ≤ m ≤ 20000` - `1 ≤ q ≤ 20000` - `1 ≤ l ≤ r ≤ n` - `1 ≤ v ≤ 1000000000` - `1 ≤ w ≤ n` - `1 ≤ need ≤ 100000000000000`
Input
The first line contains three integers n, m and q.
Each of the next m lines contains three integers l, r and v, one delivery day in order.
Each of the next q lines contains two integers w and need, one standing order.
Output
Print q lines, one per order in the order they were given. Each line holds the earliest day number, counting from 1, by which that depot has received at least need crates, or -1 if no day reaches it.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.