Constraints

• 1 <= len(operations) <= 200000
• 0 <= timestamp, currentTimestamp, startTimestamp, endTimestamp <= 10^18
• Timestamps in record operations are non-decreasing
• 1 <= windowSeconds <= 10^18 for count operations
• Multiple events may occur at the same timestamp

Examples

Solution

def solution(operations):
    from bisect import bisect_left, bisect_right

    times = []
    prefix = []
    results = []

    def range_count(start, end):
        if end < start or not times:
            return 0

        left = bisect_left(times, start)
        right = bisect_right(times, end) - 1

        if left >= len(times) or right < left:
            return 0

        return prefix[right] - (prefix[left - 1] if left > 0 else 0)

    for op in operations:
        kind = op[0]

        if kind == "record":
            t = op[1]
            if times and times[-1] == t:
                prefix[-1] += 1
            else:
                times.append(t)
                prefix.append((prefix[-1] if prefix else 0) + 1)

        elif kind == "count":
            window_seconds, current_timestamp = op[1], op[2]
            if window_seconds <= 0:
                results.append(0)
            else:
                start = current_timestamp - window_seconds + 1
                results.append(range_count(start, current_timestamp))

        elif kind == "countRange":
            start_timestamp, end_timestamp = op[1], op[2]
            results.append(range_count(start_timestamp, end_timestamp))

        else:
            raise ValueError("Unknown operation type")

    return results

Time complexity: record: O(1) amortized; count/countRange: O(log m), where m is the number of distinct recorded timestamps. Space complexity: O(m), where m is the number of distinct recorded timestamps.

Hints

1. Because record timestamps never decrease, you can keep timestamps in sorted order without inserting in the middle. If the same timestamp repeats, merge it into the last bucket.
2. To answer an inclusive range query quickly, find the first recorded timestamp >= start and the last recorded timestamp <= end, then use cumulative totals.