Design an in-memory banking service

Design an in-memory banking service supporting timestamped operations and edge-case semantics. Implement: (1) create_account(id, t): Create a new account at timestamp t. Return false if id currently exists and has not been merged since its last existence. After an account id is merged away, it may be created again at a later timestamp with balance initialized to 0, without erasing pre-merge historical activities. (2) deposit(id, amount, t) and pay(id, amount, t): Update balance at timestamp t; amounts are non-negative integers; reject pay if insufficient funds. (3) transfer(src, dst, amount, t) to initiate a pending transfer that immediately debits src’s available balance; accept_transfer(dst, transfer_id, t 2) to finalize the transfer into dst at timestamp t2. Activity counting rule: only finalized transfers (at t 2) contribute to activity; initiating a transfer does not. (4) top_activity(t, k): At timestamp t, return the k account ids with the largest 'activity' at t, where an account’s activity at t is the sum of absolute amounts of all operations occurring exactly at timestamp t for that account (e.g., deposit 200 and pay 100 at the same t yields activity 300). If an account id was merged before t, it must not appear for t or later; its historical activity prior to the merge remains queryable at earlier timestamps. (5) merge_accounts(dst, src, t): Merge src into dst at timestamp t. After merge, queries for src at any timestamp ≥ t (balance, activity, etc.) return None; dst’s balance/history continue. The id src may be re-created later via create_account(src, t'), in which case its balance resets to 0 starting at t', without altering pre-merge history. (6) get_balance(id, t): Return the account’s balance as of timestamp t. Specify: (a) data structures to support these semantics efficiently; (b) exact return values for invalid operations and the edge cases noted above; (c) time/space complexity of each operation; (d) a unit-testing plan that covers the tricky merge and activity rules.

Part 1: Reusable Account IDs After Merge-Away

Given a chronological list of account operations, return one boolean verdict per operation indicating whether it succeeds.

Each account ID is alive only while it is active. The two operations toggle this state, and reusing an ID after it has been merged away is allowed.

Function

def solution(operations):
    ...

Input

operations is a list, in chronological order, of triples:

(kind, account_id, timestamp)

• kind — either 'create' or 'merge_away'.
• account_id — a non-empty string (length at most 20).
• timestamp — an integer. Timestamps are non-decreasing but do not affect any verdict and can be ignored.

Output

Return a list of booleans the same length as operations, where the i-th entry is the verdict for the i-th operation (in input order).

Operation rules

Maintain the set of currently active IDs (initially empty), then process each operation in order:

• create: An ID may be created only if it is not currently active.

  • If the ID is not active → it becomes active and the operation succeeds (True).
  • If the ID is already active → the operation fails (False) and the active set is unchanged.

• merge_away: An ID is merged into some other account elsewhere and stops existing. This may only be applied to an ID that is currently active.

  • If the ID is active → it becomes inactive and the operation succeeds (True).
  • If the ID is not active → the operation fails (False) and the active set is unchanged.

Because a successful merge_away removes the ID from the active set, that same ID may be created again later as a fresh account, and the new create succeeds.

You only need to decide success or failure of each operation; you are not asked to track balances or historical activity.

Examples

operations = [('create', 'A', 1), ('create', 'A', 2)]
-> [True, False]          # second create fails: 'A' is already active

operations = [('create', 'A', 1), ('merge_away', 'A', 5), ('create', 'A', 7)]
-> [True, True, True]     # 'A' is reusable after being merged away

operations = [('merge_away', 'X', 1), ('create', 'X', 2)]
-> [False, True]          # nothing active to merge away, then create succeeds

Constraints

• 1 <= len(operations) <= 200000
• Account IDs are non-empty strings of length at most 20.
• Timestamps are integers in non-decreasing order.

Hints

1. You only need to know whether an ID is currently active or not.
2. A successful merge_away frees that ID for a later create.

Approach

Approach — simulate the live set of active IDs.

The only state that matters for deciding success is which IDs are currently active. We track that with a single hash set called active, then walk the operations in chronological order, appending one boolean verdict per operation to result.

For each operation we branch on op[0], the operation kind:

• create: An ID may be created only if it is not currently active. So if acc_id in active, the create fails (False) and we leave the set unchanged. Otherwise we add it and record True. Because a merged-away ID was already removed from the set, a later re-create of the same ID correctly succeeds — this is what makes IDs reusable after merge_away.
• merge_away: This succeeds only if the ID is currently active. If acc_id in active, we remove it (it stops existing) and record True; otherwise nothing is active to merge and we record False.
• Any other kind raises ValueError.

Why it's correct. The set is an exact invariant of "IDs that exist right now." create toggles an absent ID to present; merge_away toggles a present ID to absent. Each verdict depends only on current membership, which is precisely the rule the problem states. Timestamps are never consulted — they're already non-decreasing and don't affect success — so they're simply ignored.

The output list mirrors the input one-to-one, preserving order via append.

• Time complexity: O(n) average, where n is the number of operations — each does one O(1) average-time set membership test plus at most one O(1) add/remove.
• Space complexity: O(m), where m is the peak number of simultaneously active IDs (the size of active); the result list adds O(n) for the returned output.

Part 2: Timestamped Deposits and Payments

Simulate the balance updates of a simple in-memory bank, processing a stream of timestamped operations and returning the result of each one.

Implement:

def solution(operations):
    ...

Input

operations is a list of operations given in chronological order. Each operation is a tuple whose first element is a string tag identifying its type:

• Create: ('create', acc_id, timestamp) — request to open a new account acc_id.
• Deposit: ('deposit', acc_id, amount, timestamp) — add amount to account acc_id.
• Pay: ('pay', acc_id, amount, timestamp) — withdraw amount from account acc_id.

amount is a non-negative integer (zero is allowed). timestamp is an integer; timestamps are non-decreasing. Because the operations already arrive in chronological order, the timestamp is informational only — you do not need to read or sort by it.

Output

Return a list with exactly one entry per operation, in the same order as the input. The entry depends on the operation type:

• create → True if the account was newly opened, or False if an account with that acc_id already exists (the existing account is left unchanged).
• deposit → None if the account does not exist (the deposit is rejected). Otherwise, add amount to the balance and return the new balance (an integer). A zero-amount deposit on an existing account is valid and returns the unchanged balance.
• pay → None if the account does not exist or if the balance is less than amount (insufficient funds — the payment is rejected and the balance is unchanged). Otherwise, subtract amount from the balance and return the new balance (an integer). A payment that brings the balance to exactly 0 is allowed; a zero-amount payment always succeeds when the account exists.

Rules

• All balances start at 0 when an account is created.
• A payment is allowed only when amount <= balance (so an account may be drained to exactly 0, but not overdrawn).
• A deposit or payment on a non-existent account is rejected with None and does not create the account.

Example

For the input

[('create', 'A', 1), ('deposit', 'A', 100, 2), ('pay', 'A', 30, 3)]

the result is [True, 100, 70]: account A is opened (True), the deposit brings the balance to 100, and the payment of 30 leaves 70.

Constraints

• 1 <= len(operations) <= 200000
• 0 <= amount <= 10^9
• Timestamps are integers in non-decreasing order.

Hints

1. A hash map from account ID to current balance is enough for this sub-problem.
2. Treat amount 0 like a normal operation; it still succeeds if the account exists.

Approach

Approach. This is a straightforward simulation of an in-memory bank using a single hash map. balances maps each account id to its current integer balance, and result collects the outcome of every operation in order. We iterate once over operations, dispatching on the operation tag op[0].

Per-operation logic:

• create — ('create', acc_id, ts). If acc_idis already a key, the account exists, so we appendFalse. Otherwise we initialize balances[acc_id] = 0and appendTrue`.
• deposit — ('deposit', acc_id, amount, ts). If the account doesn't exist we append None (rejected). Otherwise we add amount and append the new balance. Since amount >= 0, a zero deposit is a valid no-op that still returns the (unchanged) balance.
• pay — ('pay', acc_id, amount, ts). Rejected with None if the account is missing or has insufficient funds (balances[acc_id] < amount). Otherwise subtract and append the resulting balance. A zero payment always succeeds when the account exists.

Any unrecognized tag raises ValueError.

Why it's correct. Operations already arrive in chronological order, so the embedded timestamp is informational only and never needs to be read for ordering — processing tuples left to right reproduces the real-world sequence. Each operation's accept/reject decision depends solely on the current map state, which is exactly the invariant a bank balance maintains. The < (not <=) check lets a payment drain an account to exactly zero, and the existence guards make missing-account deposits/payments return None as specified.

Data structure. A dict gives O(1) average create/deposit/pay, which is what keeps the whole pass linear over up to 200,000 operations.

• Time complexity: O(n)
• Space complexity: O(m)

Part 3: Pending Transfers and Acceptance

Implement a small banking engine that supports pending (escrow-style) transfers: a transfer debits the source account immediately, but the destination is not credited until the transfer is explicitly accepted.

Function

def solution(operations):
    ...

operations is a list of operation tuples. Process them in order, maintaining account balances and a ledger of outstanding pending transfers. For each operation, append one result to an output list, and return that list.

Every operation tuple ends with an integer timestamp (timestamps are non-decreasing and do not affect the logic). The first element of each tuple is the operation kind.

Operations

('create', acc_id, timestamp) — Create a new account with balance 0.

• If acc_id already exists, change nothing and append False.
• Otherwise create it at balance 0 and append True.

('deposit', acc_id, amount, timestamp) — Add amount to an account.

• If acc_id does not exist, change nothing and append None.
• Otherwise add amount to its balance and append the new balance.

('transfer', src, dst, amount, timestamp) — Start a pending transfer from src to dst.

• The transfer is rejected (change nothing, append None) if any of these hold:
  • src == dst, or
  • src does not exist, or
  • dst does not exist, or
  • balances[src] < amount (insufficient funds).
• Otherwise it succeeds: immediately debit amount from src, create a pending transfer recording (src, dst, amount), and append the transfer's id.
  • Transfer ids are unique integers assigned in order, starting at 1 and incrementing by 1 for each successful transfer.
  • The destination is not credited at this point — the money sits in escrow until accepted.

('accept', dst, transfer_id, timestamp) — Complete a pending transfer.

• Append False (and change nothing) if any of these hold:
  • transfer_id is not an outstanding pending transfer, or
  • the supplied dst does not match the transfer's recorded destination, or
  • that destination account no longer exists.
• Otherwise credit the recorded amount to the destination account, remove the pending transfer, and append True.

('balance', acc_id, timestamp) — Look up an account's balance.

• Append the current balance of acc_id, or None if the account does not exist.

Important rules

• A failed accept must not destroy the pending transfer. If accept is called with the wrong destination (or otherwise fails the checks above), it returns False but leaves the pending transfer intact, so a later correct accept can still complete it.
• An amount of 0 is valid for both deposit and transfer (a 0-amount transfer with both accounts present succeeds and produces a normal transfer id).

Examples

For operations = [('create','A',1), ('create','B',1), ('deposit','A',100,2), ('transfer','A','B',40,3), ('balance','A',4), ('accept','B',1,5), ('balance','B',6)] the result is [True, True, 100, 1, 60, True, 40].

For operations = [('create','A',1), ('create','B',1), ('deposit','A',20,2), ('transfer','A','B',30,3), ('balance','A',4), ('accept','B',1,5)] the result is [True, True, 20, None, 20, False] — the transfer is rejected for insufficient funds (returns None), A keeps its 20, and the later accept of the non-existent transfer 1 returns False.

Constraints

• 1 <= len(operations) <= 200000
• 0 <= amount <= 10^9
• Timestamps are integers in non-decreasing order.

Hints

1. Store current balances separately from pending transfers.
2. A transfer should reduce the source balance immediately, even before acceptance.

Approach

This is a single-pass simulation over the operation list. State lives in two dicts plus a counter:

• balances — account_id -> current balance
• pending — transfer_id -> (src, dst, amount) (an escrow ledger)
• next_transfer_id — monotonically increasing, starting at 1

Each op is dispatched on op[0] and does only O(1) dict work:

• create: rejects (False) if the account already exists, else inserts it at balance 0 and returns True.
• deposit: None if the account is missing, else adds amount and returns the new balance.
• transfer: validates src != dst, both accounts exist, and balances[src] >= amount. If any check fails it returns None and changes nothing. On success it immediately debits src, escrows (src, dst, amount) under the next id, returns that id, and increments the counter. The destination is not credited yet — the money sits in pending.
• accept: returns False if transfer_id isn't pending. Otherwise it reads the stored real_dst/amount and requires the supplied dst == real_dst (and the destination still exists). Only then does it credit real_dst, del the pending entry, and return True.

Why it's correct: the wrong-acceptance guard checks the destination before mutating anything and only deletes pending[transfer_id] on success, so a mismatched accept returns False while leaving the escrow intact for a later correct accept (verified by tests 3 and 4). Debiting at transfer time and crediting only on accept makes funds conserved at every step, and a transfer of amount 0 is handled naturally (balances[src] >= 0 always holds).

• Time complexity: O(n), where n is the number of operations — each operation does O(1) average-case dict lookups/updates.
• Space complexity: O(a + p), where a is the number of accounts and p is the number of outstanding pending transfers (plus the O(n) result list).

Part 4: Top Activity at an Exact Timestamp

Given a log of completed banking records and a list of independent queries, report, for each query, the accounts with the highest activity at an exact timestamp.

Activity at a timestamp

For a timestamp t, an account's activity at t is the sum of the amounts of all operations that occur at exactly t for that account. (Amounts are non-negative, so this is simply their sum.)

Inputs

records

A list of operation tuples, sorted by non-decreasing timestamp. Each tuple's first element is a kind string. The recognized kinds and how each contributes to activity are:

• ('create', acc_id, t) — Begins a new lifetime for acc_id at time t. Adds no activity.
• ('deposit', acc_id, amount, t) — Adds amount to acc_id's activity at t.
• ('pay', acc_id, amount, t) — Adds amount to acc_id's activity at t.
• ('accepted_transfer', src, dst, amount, t) — Adds amount to both src and dst's activity at t.
• ('merge_away', acc_id, t) — Makes acc_id ineligible to appear in any query result for timestamp t or any later timestamp. Adds no activity.

queries

A list of (t, k) pairs. Each query is independent.

Account lifetimes and eligibility

An account becomes active when it is created and remains active until it is merge_away'd:

• A merge_away(acc_id, t) ends the current lifetime at t, inclusive — the account is not eligible at t itself, nor at any later time, for that lifetime.
• Therefore an account created at time s and merged away at time e is eligible only for timestamps in the half-open range s <= t < e.
• An account that is never merged away stays active for all timestamps at or after its create time.
• A later create of the same ID starts a fresh, independent lifetime. An ID can thus be active in one range, ineligible in a gap, and active again in a later range.

Output

Return a list with one entry per query, in the same order as queries.

For a query (t, k), produce the list of account IDs that satisfy all of:

1. The account is active (eligible) at timestamp t, and
2. The account has positive activity at exactly t (activity > 0).

Order these IDs by:

• descending activity at t, then
• ascending lexicographic order of the ID to break ties.

Return at most the first k IDs from this ordering. If no account qualifies (including when no operations occur at t), return an empty list for that query.

Constraints

• 1 <= len(records), len(queries) <= 200000
• 0 <= amount <= 10^9
• Records are valid and sorted by non-decreasing timestamp.

Examples

• deposit A 200 and pay A 100 at t=5, plus deposit B 250 at t=5 (both accounts active), query (5, 2) → [['A', 'B']] (A has activity 300, B has 250).
• accepted_transfer A B 40 at t=3 (both active), query (3, 2) → [['A', 'B']] (both have activity 40; tie broken lexicographically).
• A and B both deposit at t=4, then merge_away A at t=4; queries (4, 2), (3, 1) → [['B'], []] (A is ineligible from t=4 on; nothing happens at t=3).
• A active at t=2, merged away at t=3, re-created at t=5 and deposits there; queries (2, 1), (4, 1), (5, 1) → [['A'], [], ['A']] (active in [1,3), ineligible at t=4, active again from t=5).

Hints

1. Store activity by exact timestamp rather than cumulatively over time.
2. Because IDs can be merged away and later recreated, think in terms of active time intervals for each ID.

Approach

Approach

The solution does a single pass over records to build two structures, then answers each query against them.

1. Per-timestamp activity. activity[t][acc_id] accumulates the sum of absolute amounts at exactly t:

• deposit / pay add amount to the named account.
• accepted_transfer adds amount to both src and dst.
• create contributes nothing.

2. Eligibility intervals (lifetimes). Each ID can be created, merged away, and re-created. We track the open lifetime in active_start[acc_id]. On merge_away, we close it as the half-open interval (start, t) and clear the open start; any still-open lifetime at the end is closed with INF. Because merge_away(id, t) bans the ID at t and after, the interval end is exclusive: is_active returns true only when start <= t < end.

Active lookup. For each ID we store sorted starts/ends. is_active(acc_id, t) does bisect_right(starts, t) - 1 to find the latest lifetime starting at or before t, then checks t < ends[i]. This correctly handles re-created IDs (a later create starts a fresh lifetime) — verified by test 4 where A is active at t=2 and t=5 but not the merged gap at t=4.

Answering queries. Results are memoized per timestamp in cache. For a new t, we collect accounts with positive activity that are active, sort by (-amt, acc_id) (descending activity, then lexicographic ID via the tuple), and store the ID order. Each query slices the cached list to k. The negated-amount tuple sort gives the exact required ordering.

• Time complexity: O(R + Σ_t (a_t·log a_t + a_t·log L)), where R = total records, a_t = accounts with activity at distinct queried timestamp t, and L = lifetimes per ID (from the bisect in is_active). Reusing the per-t cache means repeated timestamps cost only the O(k) slice.
• Space complexity: O(R) — activity entries, lifetime intervals, and the per-timestamp answer cache are all bounded by the number of records.

Part 5: Live Account Merges and Re-Creation

Process a live stream of banking operations on accounts, where accounts can be created, deposited into, merged, and queried — returning one result per operation in order.

Implement:

def solution(operations):

Input

operations is a list of operation tuples. Each tuple's first element is a string naming the operation type; the remaining elements depend on the type. Every operation ends with an integer timestamp t. Timestamps are non-decreasing but do not affect the result of any operation.

Account IDs are arbitrary hashable values (e.g. strings). An account is live from the moment it is created until it is removed by a merge; it is not live before its first creation or after being merged away.

Operations

Process the operations strictly in order. Each produces exactly one entry appended to the result list:

• ('create', acc_id, t) — Create a new account with balance 0.

  • If acc_id is already live, do nothing and append False.
  • Otherwise create it (starting at balance 0) and append True. A re-created account always starts fresh at 0.

• ('deposit', acc_id, amount, t) — Add amount to an account's balance.

  • If acc_id is not live, do nothing and append None.
  • Otherwise add amount to its balance and append the new balance.

• ('merge', dst, src, t) — Move the full current balance of src into dst, then remove src from the live system immediately.

  • If dst == src, or dst is not live, or src is not live, do nothing and append False.
  • Otherwise add src's balance to dst's balance, remove src (it becomes non-live immediately, so subsequent deposits/queries on src return None until it is created again), and append True.

• ('balance', acc_id, t) — Query an account's current balance.

  • Append the account's current balance if it is live, otherwise append None.

Output

Return a list with one element per operation, in the same order as the input, using the per-operation result values described above.

Notes

• This problem only concerns the live state observed while processing operations in order. Pre-merge history is conceptually preserved but is never queried here.
• After a merge, src is gone immediately; a later create for that same ID starts a brand-new account at balance 0.

Constraints

• 1 <= len(operations) <= 200000
• 0 <= amount <= 10^9
• Timestamps are integers in non-decreasing order.

Examples

Example 1

Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 50, 2), ('deposit', 'B', 20, 3), ('merge', 'A', 'B', 4), ('balance', 'A', 5), ('balance', 'B', 5)],)
Output: [True, True, 50, 20, True, 70, None]

Explanation: B is absorbed into A, so only A remains live with combined balance.

Example 2

Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'B', 15, 2), ('merge', 'A', 'B', 3), ('create', 'B', 4), ('balance', 'B', 4), ('deposit', 'B', 5, 5), ('balance', 'A', 6)],)
Output: [True, True, 15, True, True, 0, 5, 15]

Explanation: After being merged away, B can be recreated later as a fresh live account.

Hints

1. For this sub-problem, a merge is just a move of current balance plus deletion of the source ID from the live map.
2. Re-creating a merged-away ID is the same as inserting a new key with balance 0.

Approach

The solution maintains a single dictionary balances mapping each live account ID to its current balance, then replays the operation stream in order, appending one result per operation.

Why a dict is the right structure: membership in balances is the definition of "live". An account exists exactly while it has a key; merge/del and create insertions flip that membership, and every operation just reads/writes this one map in O(1).

Per operation type:

• create: if the ID is already a key, the account is live, so it's a duplicate → append False. Otherwise insert it at 0 and append True. A re-created account naturally starts fresh at 0 because the previous incarnation's key was removed by its merge.
• deposit: if the ID isn't live, the deposit is invalid → append None. Otherwise add amount and append the new balance.
• merge(dst, src): reject (append False) if dst == src, or either side isn't live. Otherwise fold balances[src] into balances[dst], del balances[src] (so src becomes invalid immediately), and append True.
• balance: balances.get(acc_id) returns the balance for live accounts and None for non-live ones in one expression.

Correctness hinges on ordering and the membership invariant. Because operations are processed sequentially, the dict always reflects exactly the live state at that moment — matching the "live state observed while processing in order" requirement. The del on merge guarantees later src deposits/balances return None until a fresh create. Timestamps are carried in the tuples but aren't needed for the live-state queries, so they're ignored.

• Time complexity: O(n), where n is the number of operations. Each operation does O(1) average-case dictionary work (hash lookup/insert/delete).
• Space complexity: O(m), where m is the peak number of simultaneously live accounts stored in the dict, plus O(n) for the output list of results.

Part 6: Balance Queries As of a Timestamp

Implement solution(events, queries) to answer point-in-time balance queries against an account event log.

You are given a chronological log of account events and a list of independent queries. For each query (id, t), return the balance of account id as of timestamp t — the state after every event whose timestamp is <= t has been applied. Queries do not modify state and are answered independently.

Input

• events — a list of event tuples, already sorted by non-decreasing timestamp. Each event is one of:
  • ('create', id, t) — opens a new account id (or a fresh lifetime for a reused id) with balance 0 at time t.
  • ('deposit', id, amount, t) — adds amount to id's balance at time t.
  • ('pay', id, amount, t) — subtracts amount from id's balance at time t.
  • ('merge', dst, src, t) — folds account src into account dst at time t.
• queries — a list of (id, t) tuples to answer.

Output

Return a list with one entry per query, in the same order:

• the integer balance of id as of t, or
• None if id is not valid at t (see rules below).

Rules

• Same-timestamp events are all applied first. A query at time t reflects every event with timestamp <= t, including events that share the timestamp t. (E.g. a deposit and a pay both at t=1 are both included for a query at t=1.)
• Before creation → None. If t is earlier than the account's create time (or the id never appears), return None.
• Merge semantics. After merge(dst, src, t):
  • dst's balance at time t becomes dst_balance + src_balance (each taken just before the merge).
  • src becomes invalid for every timestamp >= t; a query on src at any t' >= t returns None. Queries on src for timestamps before t still return its historical balance.
• Reused IDs start a brand-new lifetime. If an id that was previously merged away is created again later, it begins a fresh account with balance 0. This new lifetime does not affect answers for any earlier timestamp — queries before the re-creation still resolve against the original lifetime.

Constraints

• 1 <= len(events), len(queries) <= 200000
• 0 <= amount <= 10^9
• The event log is valid and sorted by non-decreasing timestamp.

Examples

Example 1

Input: ([('create', 'A', 1), ('deposit', 'A', 100, 2), ('pay', 'A', 30, 5)], [('A', 0), ('A', 1), ('A', 4), ('A', 5), ('B', 5)])
Output: [None, 0, 100, 70, None]

Explanation: Queries before creation or for unknown IDs return None.

Example 2

Input: ([('create', 'A', 1), ('deposit', 'A', 20, 2), ('create', 'B', 3), ('deposit', 'B', 5, 4), ('merge', 'A', 'B', 6)], [('B', 5), ('B', 6), ('A', 6), ('A', 7)])
Output: [5, None, 25, 25]

Explanation: B exists before timestamp 6, but is invalid from timestamp 6 onward after the merge.

Hints

1. Because an ID can disappear and later come back, model each ID as a sequence of lifetimes.
2. Within a lifetime, store balance changes by timestamp so you can answer queries with binary search.

Approach

Approach — per-lifetime balance snapshots + two binary searches.

The tricky part is that an account ID can live several separate lifetimes: create opens one, merge(dst, src, t) closes src's lifetime at t, and a later create of the same ID starts a fresh one. We must answer "balance of id as of t" against the right lifetime.

Building the index (one pass over events). For each ID we keep a list of lifetimes. Each lifetime is a dict with start, end (INF until a merge ends it), and two parallel arrays times/balances recording the running balance after every update:

• create: open a new lifetime seeded with (t, 0); mark it current[id].
• deposit/pay: append t and prev ± amount to the current lifetime.
• merge(dst, src, t): push dst_balance + src_balance onto dst's arrays at time t, set src.end = t, and drop src from current so a future re-create starts clean.

Because events are sorted by non-decreasing time, each lifetime's times array is non-decreasing, and lifetimes for one ID have increasing starts.

Answering a query (id, t).

1. bisect_right(starts, t) - 1 finds the latest lifetime that began at or before t.
2. If none exists, or t >= ends[i] (the lifetime was already merged away / closed), return None.
3. Otherwise bisect_right(life['times'], t) - 1 finds the last update at or before t, and we return balances[j].

Why correct: using bisect_right means same-timestamp events are all applied before the query "sees" t (test 4: deposit+pay at t=1 → 3), and the t >= end check makes a merged source invalid exactly from the merge time onward (test 3: query at the merge timestamp returns None).

• Time complexity: O(E + Q·(log r + log u)) where E = number of events, Q = number of queries, r = lifetimes for the queried ID, u = updates in the chosen lifetime. Building the index is O(E) (one pass, amortized O(1) appends); each query does two binary searches.
• Space complexity: O(E) — every event contributes at most one entry to some lifetime's times/balances arrays (or starts a new lifetime), so total stored snapshots are linear in the number of events.