735. The First Leg That Runs Out of Seats
A route has n legs, numbered from 1, and leg i can carry at most cap[i] people. Each of
q bookings is l r v, meaning v people travel on every leg from l to r inclusive.
Print the number of the FIRST leg that ends up over capacity, or 0 if every leg is within it.
cap = 5 5 5, bookings (1 2 3) and (2 3 3) -> 2
cap = 1 1, booking (1 2 1) -> 0
cap = 1 1, booking (1 2 2) -> 1
## Two writes per booking
Each booking is a constant range add, so it costs two writes on a difference array exactly as
in problem 721. Walking every booked leg is O(n q).
## The check rides along with the recovery
No second pass is needed. The running total that recovers leg i's load is available AT leg
i, so compare it against cap[i] right there and stop:
run = 0
for i in 1 .. n:
run += d[i]
if run > cap[i]: print i and stop
print 0
## Where this differs from problem 1439
1439 asks a yes-or-no question: does a vehicle ever exceed its capacity. That answer can be computed by any order of checking, because it only asks whether a failure exists.
This asks WHICH leg fails first, which forces the scan left to right and forces it to stop. Collecting every failure and taking the minimum is correct and does more work; scanning right to left and keeping the last is a quiet way to get it wrong when several legs fail.
Reading whether a problem wants existence or identity, before writing the loop, is what the pair is here to teach.
## Capacity is per leg, not per booking
Two bookings that each fit can overlap on one leg and exceed it there. That is the whole reason
the loads must be accumulated before anything is checked, and 5 5 5 with two bookings of 3
failing at leg 2 is that case.
## Overflow, and why it hides here
2 * 10^5 bookings of 10^9 stack to 2 * 10^14 on a single leg, while the capacities
themselves stay small. In 32 bits the accumulated load wraps negative and the overloaded leg
compares as comfortably under capacity, so the program reports 0 and looks fine.
An overflow that produces a WRONG ANSWER rather than a crash is the kind worth expecting in advance.
## Boundaries
Zero bookings always answers 0. A leg of capacity 0 fails on any booking touching it.
## Cost
Time O(n + q). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ q ≤ 200000` - `1 ≤ l ≤ r ≤ n` - `1 ≤ v ≤ 10^9` - `0 ≤ cap[i] ≤ 10^9`
Input
The first line contains two integers n and q.
The second line contains n integers, the capacities.
Each of the next q lines contains three integers l, r and v.
Output
Print one integer, the first leg over capacity, or 0.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.