Constraints

• 1 <= len(operations) <= 20000
• 0 <= amount <= 10^9
• 0 <= expiry_time, timestamp <= 10^9
• Operations are processed in the given order
• A lot is usable exactly when timestamp < expiry_time

Examples

Solution

def solution(operations):
    import heapq
    from collections import defaultdict

    heaps = defaultdict(list)  # user_id -> min-heap of [expiry_time, insertion_order, amount]
    totals = defaultdict(int)  # user_id -> total unexpired amount currently tracked
    results = []
    insertion_order = 0
    current_time = None

    def prune(user_id, timestamp):
        heap = heaps[user_id]
        while heap and heap[0][0] <= timestamp:
            expiry_time, order, amount = heapq.heappop(heap)
            totals[user_id] -= amount

    for op in operations:
        kind = op[0]

        if kind == 'add':
            _, user_id, amount, expiry_time = op

            if amount <= 0:
                continue

            # Because non-add timestamps are nondecreasing and operations are processed
            # in order, a lot added after time has advanced past its expiry is useless.
            if current_time is not None and expiry_time <= current_time:
                continue

            heapq.heappush(heaps[user_id], [expiry_time, insertion_order, amount])
            totals[user_id] += amount
            insertion_order += 1

        elif kind == 'subtract':
            _, user_id, amount, timestamp = op
            current_time = timestamp
            prune(user_id, timestamp)

            if amount == 0:
                results.append(True)
                continue

            if totals[user_id] < amount:
                results.append(False)
                continue

            totals[user_id] -= amount
            remaining_to_spend = amount
            heap = heaps[user_id]

            while remaining_to_spend > 0:
                expiry_time, order, lot_amount = heapq.heappop(heap)
                if lot_amount <= remaining_to_spend:
                    remaining_to_spend -= lot_amount
                else:
                    lot_amount -= remaining_to_spend
                    remaining_to_spend = 0
                    heapq.heappush(heap, [expiry_time, order, lot_amount])

            results.append(True)

        elif kind == 'balance':
            _, user_id, timestamp = op
            current_time = timestamp
            prune(user_id, timestamp)

            breakdown = [
                (amount, expiry_time)
                for expiry_time, order, amount in sorted(heaps[user_id])
            ]
            results.append((totals[user_id], breakdown))

        else:
            raise ValueError('Unknown operation type: ' + str(kind))

    return results

Time complexity: Add: O(log m). Subtract: O((p + c) log m), where p is the number of newly pruned expired lots and c is the number of lots consumed. Balance: O(m log m) to sort the active lots for that user. Here m is the number of active lots for the queried user.. Space complexity: O(M), where M is the total number of unexpired lots currently stored across all users..

Hints

1. Store each user's credits as separate lots instead of merging everything into one number, because expiry times matter during subtraction.
2. For atomic subtraction, first compute whether enough unexpired balance exists before changing any lot.