P8661 [Lanqiao Cup 2018 NOI Qualifier B] Log Statistics

Xiaoming maintains a programmer forum. Now he has collected a set of "like" logs with a total of $N$ lines. Each line is in the format `ts id`, meaning that at time $ts$, the post with number $id$ received one "like". Now Xiaoming wants to count which posts have ever been "hot posts". If a post has received at least $K$ likes within any time period of length $D$, Xiaoming considers that this post has once been a "hot post". More specifically, if there exists a time $T$ such that the post receives at least $K$ likes during the time interval $[T, T + D)$ (note that it is a left-closed right-open interval), then this post has once been a "hot post". Given the logs, please help Xiaoming list the IDs of all posts that have ever been "hot posts".

The first line contains three integers $N$, $D$, and $K$. The following $N$ lines each contain one log entry, with two integers $ts$ and $id$.

Output the IDs of hot posts in increasing order. Print one $id$ per line.

For $50\%$ of the testdata, $1 \le K \le N \le 1000$. For $100\%$ of the testdata, $1 \le K \le N \le 10^5$, and $0 \le id, ts \le 10^5$. Time limit: 1 second, 256 MB. Lanqiao Cup 2018, 9th Provincial Contest. Translated by ChatGPT 5