시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 23 | 7 | 7 | 43.750% |
Vasya owns a magical hourglass store and he is crazy about hourglasses. Vasya wants everything in his store to work like a clock. Whenever some hourglass in his store becomes empty, Vasya immediately turns it over.
His store has $n$ hourglasses. Hourglass $i$ has sand for exactly $b_i$ minutes and will magically appear in the store $a_i$ minutes after Vasya's work day starts. Each hourglass appears empty, so Vasya has to turn it over immediately. Vasya is working for $t$ minutes every day.
Vasya is very tired of walking around his store and turning his hourglasses over and over again. So he would like to know how many hourglasses he will have to turn over at every minute from the start of his work day.
First line contains two integers $n$ and $t$ --- number of hourglasses in Vasya's store and number of minutes in Vasya's work day ($1 \le n, t \le 2 \cdot 10^5$).
Next $n$ lines contain the description of Vasya's hourglasses: two integers $a_i$ and $b_i$ --- the moment when $i$-th hourglass appears, and the number of minutes it works without turning it over ($1 \le a_i, b_i \le 2 \cdot 10^5$).
Output $t$ integers, where $i$-th number is equal to the number of hourglasses Vasya has to turn over after $i$ minutes pass.
번호 | 배점 | 제한 |
---|---|---|
1 | 16 | $n \le 5000$, $t \le 5000$ |
2 | 23 | $n \le 2 \cdot 10^5$, $t \le 5000$ |
3 | 27 | $n \le 2 \cdot 10^5$, $t \le 2 \cdot 10^5$, all $b_i$ are different |
4 | 34 | $n \le 2 \cdot 10^5$, $t \le 2 \cdot 10^5$ |
2 5 1 2 2 4
1 1 1 0 1
4 8 2 2 1 3 3 4 5 10
1 1 1 2 1 1 2 1
2 12 2 1 1 2
1 1 2 1 2 1 2 1 2 1 2 1
In the first sample Vasya has to:
In the second sample Vasya has to: