P8685 [Lanqiao Cup 2019 NOI Qualifier A] Takeaway Shop Priority

In the “Bao Le Me” takeaway system, there are $N$ takeaway shops, numbered from $1$ to $N$. Each shop has a priority value. Initially (at time $0$), all priorities are $0$. For every $1$ unit of time: - If a shop has no orders, its priority decreases by $1$, but not below $0$. - If a shop has orders, its priority does not decrease. Instead, for each order, its priority increases by $2$. If at some time a shop’s priority is greater than $5$, it will be added to the priority cache. If its priority is less than or equal to $3$, it will be removed from the priority cache. Given $M$ order records within time $T$, compute how many shops are in the priority cache at time $T$.

The first line contains $3$ integers $N$, $M$, and $T$. The next $M$ lines each contain two integers $ts$ and $id$, meaning that at time $ts$, the shop with number $id$ received one order.

Output one integer representing the answer.

**Sample Explanation** At time $6$, shop $1$’s priority drops to $3$ and is removed from the priority cache; shop $2$’s priority increases to $6$ and is added to the priority cache. Therefore, there is $1$ shop (shop $2$) in the priority cache. **Constraints and Rules** For $80\%$ of the testdata, $1 \le N, M, T \le 10000$. For all testdata, $1 \le N, M, T \le 10^5$, $1 \le ts \le T$, $1 \le id \le N$. Lanqiao Cup 2019 Provincial Contest, Group A, Problem G. Translated by ChatGPT 5