GPU credit ledger

Build GPUCredit with three methods:

• add_credit(credit_id, amount, timestamp, expiration) creates a grant of amount credits. expiration is a duration: the grant can be used at every time t with timestamp <= t <= timestamp + expiration, and both ends are inclusive. credit_id values are unique, and nothing in this problem depends on them.
• subtract(amount, timestamp) burns amount credits at timestamp. Take them from the grants that are usable at that moment, starting with the one that expires soonest and moving on to the next one until amount is covered. A subtract never fails. If the usable grants can't cover it, whatever's left over becomes debt.
• get_balance(timestamp) -> int | None returns the remaining credits over all grants usable at timestamp, minus the debt.
  • It returns None if no grant is usable at timestamp. A grant that's fully used up but hasn't expired yet still counts as usable.
  • It returns None if the result is negative. A balance of exactly 0 is 0, not None.

Debt: a new grant first pays off any outstanding debt. So after subtract(100) against a 10-credit grant, the debt is 90, and a later 50-credit grant is swallowed whole, leaving a debt of 40.

In this level, calls arrive in time order: every call's timestamp is >= the one before. When several calls share a timestamp they happen in call order.

g = GPUCredit()
g.add_credit("a", 4, 20, 40)    # usable 20..60
g.add_credit("b", 3, 30, 10)    # usable 30..40 (expires first)
g.subtract(2, 30)               # taken from b: b=1, a=4
g.get_balance(40)               # 5
g.get_balance(41)               # 4 (b is gone)
g.get_balance(61)               # None (no usable grant)

Queries and events can number in the tens of thousands, with a query after every event, so re-summing all the grants on every call is too slow. Aim for amortized O(log n) per call.