The only difference between easy and hard versions is constraints.
If you write a solution in Python, then prefer to send it in PyPy to speed up execution time.
A session has begun at Beland State University. Many students are taking exams.
Polygraph Poligrafovich is going to examine a group of $$$n$$$ students. Students will take the exam one-by-one in order from $$$1$$$-th to $$$n$$$-th. Rules of the exam are following:
Students take the exam in the fixed order, one-by-one, without any interruption. At any moment of time, Polygraph Poligrafovich takes the answer from one student.
The duration of the whole exam for all students is $$$M$$$ minutes ($$$\max t_i \le M$$$), so students at the end of the list have a greater possibility to run out of time to pass the exam.
For each student $$$i$$$, you should count the minimum possible number of students who need to fail the exam so the $$$i$$$-th student has enough time to pass the exam.
For each student $$$i$$$, find the answer independently. That is, if when finding the answer for the student $$$i_1$$$ some student $$$j$$$ should leave, then while finding the answer for $$$i_2$$$ ($$$i_2>i_1$$$) the student $$$j$$$ student does not have to go home.
The first line of the input contains two integers $$$n$$$ and $$$M$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le M \le 2 \cdot 10^7$$$) — the number of students and the total duration of the exam in minutes, respectively.
The second line of the input contains $$$n$$$ integers $$$t_i$$$ ($$$1 \le t_i \le 100$$$) — time in minutes that $$$i$$$-th student spends to answer to a ticket.
It's guaranteed that all values of $$$t_i$$$ are not greater than $$$M$$$.
Print $$$n$$$ numbers: the $$$i$$$-th number must be equal to the minimum number of students who have to leave the exam in order to $$$i$$$-th student has enough time to pass the exam.
7 15 1 2 3 4 5 6 7
0 0 0 0 0 2 3
5 100 80 40 40 40 60
0 1 1 2 3
The explanation for the example 1.
Please note that the sum of the first five exam times does not exceed $$$M=15$$$ (the sum is $$$1+2+3+4+5=15$$$). Thus, the first five students can pass the exam even if all the students before them also pass the exam. In other words, the first five numbers in the answer are $$$0$$$.
In order for the $$$6$$$-th student to pass the exam, it is necessary that at least $$$2$$$ students must fail it before (for example, the $$$3$$$-rd and $$$4$$$-th, then the $$$6$$$-th will finish its exam in $$$1+2+5+6=14$$$ minutes, which does not exceed $$$M$$$).
In order for the $$$7$$$-th student to pass the exam, it is necessary that at least $$$3$$$ students must fail it before (for example, the $$$2$$$-nd, $$$5$$$-th and $$$6$$$-th, then the $$$7$$$-th will finish its exam in $$$1+3+4+7=15$$$ minutes, which does not exceed $$$M$$$).
AC Rate 20.51%
Date 07/21/2019 13:44:02