A beacon logs pings and answers recency queries over a trailing window of width w. It processes q operations, each one of:
HIT t — record a ping at time t.COUNT t — report how many pings recorded so far have a time strictly greater than t - w and less than or equal to t (that is, within the trailing window (t - w, t]).All timestamps t are given in non-decreasing order across the operations.
Line 1: two integers q and w.
Next q lines: HIT t or COUNT t.
For each COUNT operation, in order, print the number of pings in its trailing window.
Example 1
Input
6 5 HIT 1 HIT 2 HIT 3 COUNT 4 HIT 8 COUNT 10
Expected
3 1
Explanation
With w=5: pings arrive at 1, 2, 3. COUNT 4 counts window (-1, 4], i.e. all three, so 3. After a ping at 8, COUNT 10 counts window (5, 10], only the ping at 8, so 1.
Example 2
Input
4 3 HIT 2 COUNT 2 HIT 5 COUNT 5
Expected
1 1
Explanation
With w=3: COUNT 2 over window (-1, 2] counts the ping at 2, so 1. COUNT 5 over window (2, 5] counts the ping at 5 (the ping at 2 is excluded), so 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →