Sliding Window Rate Limiter (Per User, and Per User+Game with Combined Constraints)

Problem: Sliding Window Rate Limiter (Per User, and Per User+Game with Combined Constraints) Implement a sliding-window rate limiter to decide whether each request should be allowed. Part 1: Per-User Rate Limiting Rate limit each userId independently. The system receives a sequence of request events, each containing: timestamp: the time of the request (integer seconds) userId Given parameters: windowSize (in seconds) and maxRequests (maximum allowed requests within the window) For each request at time timestamp, consider the interval (timestamp - windowSize, timestamp] for that user. If the number of requests in the interval is less than maxRequests, the request is ALLOWED and recorded. Otherwise, it is DENIED and not recorded. Output the decision for each request. Part 2: Combined Per-User and Per-(User, Game) Rate Limiting Extend Part 1 by adding gameId and enforcing both constraints: User-level limit: each userId allows at most maxRequestsUser requests in the sliding window User+Game-level limit: each pair (userId, gameId) allows at most maxRequestsUserGame requests in the sliding window A request (timestamp, userId, gameId) is ALLOWED only if it passes both limiters; otherwise it is denied. If denied: it is recorded in neither window If allowed: it must be recorded in both the user window and the (user, game) window Input (stdin) First line: integer part (1 or 2). If part = 1: Second line: windowSize maxRequests Third line: integer n Next n lines: timestamp userId If part = 2: Second line: windowSize maxRequestsUser maxRequestsUserGame Third line: integer n Next n lines: timestamp userId gameId Output (stdout) Print n lines, each either ALLOW or DENY. Constraints 1 <= n <= 2 * 10^5 1 <= windowSize <= 10^9 Timestamps are non-decreasing (multiple requests can share the same second) userId, gameId are strings without spaces Must be efficient for large event streams Example Input 1 10 3 6 1 u1 2 u1 3 u1 4 u1 11 u1 12 u1 Output ALLOW ALLOW ALLOW DENY ALLOW ALLOW