ACMICPC 2018 南京赛区网络预赛 G题
题目链接：https://nanti.jisuanke.com/t/30996
During teadrinking, princess, amongst other things, asked why has such a goodnatured and cute Dragon imprisoned Lpl in the Castle? Dragon smiled enigmatically and answered that it is a big secret. After a pause, Dragon added:
— We have a contract. A rental agreement. He always works all day long. He likes silence. Besides that, there are many more advantages of living here in the Castle. Say, it is easy to justify a missed call: a phone ring can’t reach the other side of the Castle from where the phone has been left. So, the imprisonment is just a tale. Actually, he thinks about everything. He is smart. For instance, he started replacing incandescent lamps with energysaving lamps in the whole Castle…
Lpl chose a model of energysaving lamps and started the replacement as described below. He numbered all rooms in the Castle and counted how many lamps in each room he needs to replace.
At the beginning of each month, Lpl buys mmenergysaving lamps and replaces lamps in rooms according to his list. He starts from the first room in his list. If the lamps in this room are not replaced yet and Lpl has enough energysaving lamps to replace all lamps, then he replaces all ones and takes the room out from the list. Otherwise, he’ll just skip it and check the next room in his list. This process repeats until he has no energysaving lamps or he has checked all rooms in his list. If he still has some energysaving lamps after he has checked all rooms in his list, he’ll save the rest of energysaving lamps for the next month.
As soon as all the work is done, he ceases buying new lamps. They are very high quality and have a very longlife cycle.
Your task is for a given number of month and descriptions of rooms to compute in how many rooms the old lamps will be replaced with energysaving ones and how many energysaving lamps will remain by the end of each month.
Input
Each input will consist of a single test case.
The first line contains integers nn and m (1 \le n \le 100000, 1 \le m \le 100)m(1≤n≤100000,1≤m≤100) — the number of rooms in the Castle and the number of energysaving lamps, which Lpl buys monthly.
The second line contains nn integers k_1, k_2, …, k_nk1,k2,…,kn
(1 \le k_j \le 10000, j = 1, 2, …, n)(1≤kj≤10000,j=1,2,…,n) — the number of lamps in the rooms of the Castle. The number in position jj is the number of lamps in jjth room. Room numbers are given in accordance with Lpl’s list.
The third line contains one integer q (1 \le q \le 100000)q(1≤q≤100000) — the number of queries.
The fourth line contains qq integers d_1, d_2, …, d_qd1,d2,…,dq
(1 \le d_p \le 100000, p = 1, 2, …, q)(1≤dp≤100000,p=1,2,…,q) — numbers of months, in which queries are formed.
Months are numbered starting with 11; at the beginning of the first month Lpl buys the first m energysaving lamps.
Output
Print qq lines.
Line pp contains two integers — the number of rooms, in which all old lamps are replaced already, and the number of remaining energysaving lamps by the end of d_pdp month.
Hint
Explanation for the sample:
In the first month, he bought 44 energysaving lamps and he replaced the first room in his list and remove it. And then he had 11 energysaving lamps and skipped all rooms next. So, the answer for the first month is 1,1——11,1−−−−−−1 room’s lamps were replaced already, 11 energysaving lamp remain.
样例输入复制
1  5 4 
样例输出复制
1  4 0 
题目来源
首先认真读题。 其实发现模拟一下就是每次从左往右找到一个不大于某个值的数，然后干掉。
这个题目范围还比较水。就是暴力枚举每个月，然后每个月找满足条件的数的时候用线段树维护一下。
线段树水题！
1 
