{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003e简单版本和困难版本之间唯一的区别在于约束条件。\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003e如果你用Python编写解决方案,那么最好使用PyPy来加快执行时间。\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003e贝兰德州立大学开始了一场考试。许多学生正在参加考试。\u003c/p\u003e\u003cp\u003e波利格拉福维奇将要检查一组$$$n$$$学生。学生将按照从第$$$1$$$到第$$$n$$$的顺序依次参加考试。考试规则如下:\u003c/p\u003e\u003cul\u003e \u003cli\u003e 第$$$i$$$个学生随机选择一张试卷。 \u003c/li\u003e\u003cli\u003e 如果这张试卷对学生来说太难,他就不答题立即回家(这个过程非常快,可以认为没有时间流逝)。这个学生考试不及格。 \u003c/li\u003e\u003cli\u003e 如果学生觉得试卷很简单,他需要花费$$$t_i$$$分钟来完成考试。之后,他立即得到成绩并回家。 \u003c/li\u003e\u003c/ul\u003e\u003cp\u003e学生按照固定的顺序依次参加考试,没有任何中断。在任何时刻,波利格拉福维奇都会从一个学生那里拿到答案。\u003c/p\u003e\u003cp\u003e所有学生参加考试的总时长为$$$M$$$分钟($$$\\max t_i \\le M$$$),因此名单末尾的学生更有可能因为时间不够而无法通过考试。\u003c/p\u003e\u003cp\u003e对于每个学生$$$i$$$,你需要计算需要不及格的学生的最小可能数量,以便第$$$i$$$个学生有足够的时间\u003cspan class\u003d\"tex-font-style-bf\"\u003e通过\u003c/span\u003e考试。\u003c/p\u003e\u003cp\u003e对于每个学生$$$i$$$,独立找到答案。也就是说,如果在为学生$$$i_1$$$找到答案时需要让某个学生$$$j$$$离开,那么在为$$$i_2$$$($$$i_2\u0026gt;i_1$$$)找到答案时,学生$$$j$$$不需要回家。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含两个整数$$$n$$$和$$$M$$$($$$1 \\le n \\le 2 \\cdot 10^5$$$,$$$1 \\le M \\le 2 \\cdot 10^7$$$)— 学生人数和考试总时长(以分钟为单位)。\u003c/p\u003e\u003cp\u003e输入的第二行包含$$$n$$$个整数$$$t_i$$$($$$1 \\le t_i \\le 100$$$)— 每个学生答题所需的时间(以分钟为单位)。\u003c/p\u003e\u003cp\u003e保证所有的$$$t_i$$$的值都不大于$$$M$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出$$$n$$$个数字:第$$$i$$$个数字必须等于需要离开考试的最小学生数量,以便第$$$i$$$个学生有足够的时间通过考试。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 15\n1 2 3 4 5 6 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 0 0 0 0 2 3 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 100\n80 40 40 40 60\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 1 1 2 3 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e示例1的解释。\u003c/p\u003e\u003cp\u003e请注意,前五个学生的考试时间总和不超过$$$M\u003d15$$$(总和为$$$1+2+3+4+5\u003d15$$$)。因此,前五个学生即使所有在他们之前的学生也通过考试,他们也能通过考试。换句话说,答案的前五个数字是$$$0$$$。\u003c/p\u003e\u003cp\u003e为了让第$$$6$$$个学生通过考试,至少需要有$$$2$$$名学生在他之前不及格(例如,第$$$3$$$和第$$$4$$$名学生,那么第$$$6$$$名学生完成考试需要$$$1+2+5+6\u003d14$$$分钟,不超过$$$M$$$)。\u003c/p\u003e\u003cp\u003e为了让第$$$7$$$个学生通过考试,至少需要有$$$3$$$名学生在他之前不及格(例如,第$$$2$$$和第$$$5$$$名学生,那么第$$$6$$$名学生完成考试需要$$$7$$$分钟,不超过$$$1+3+4+7\u003d15$$$)。\u003c/p\u003e"}}]}