# ACM-ICPC 2018 南京赛区网络预赛 G. Lpl and Energy-saving Lamps(二分+线段树区间最小)

During tea-drinking, princess, amongst other things, asked why has such a good-natured 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 energy-saving lamps in the whole Castle...

Lpl chose a model of energy-saving 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 mmm energy-saving 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 energy-saving 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 energy-saving lamps or he has checked all rooms in his list. If he still has some energy-saving lamps after he has checked all rooms in his list, he'll save the rest of energy-saving 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 long-life 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 energy-saving ones and how many energy-saving lamps will remain by the end of each month.

Input

Each input will consist of a single test case.

The first line contains integers n and m(1≤n≤100000,1≤m≤100) — the number of rooms in the Castle and the number of energy-saving lamps, which Lpl buys monthly.

The second line contains nnn integers k1,k2,...,kn

(1≤kj≤10000,j=1,2,...,n) — the number of lamps in the rooms of the Castle. The number in position j is the number of lamps in j-th room. Room numbers are given in accordance with Lpl's list.

The third line contains one integer q(1≤q≤100000) — the number of queries.

The fourth line contains q integers d1,d2,...,dq

(1≤dp≤100000,p=1,2,...,q)— numbers of months, in which queries are formed.

Months are numbered starting with 1; at the beginning of the first month Lpl buys the first m energy-saving lamps.

Output

Print q lines.

Line p contains two integers — the number of rooms, in which all old lamps are replaced already, and the number of remaining energy-saving lamps by the end of dp month.

Hint

Explanation for the sample:

In the first month, he bought 4 energy-saving lamps and he replaced the first room in his list and remove it. And then he had 1 energy-saving lamps and skipped all rooms next. So, the answer for the first month is 1,1−−−−−−1 room's lamps were replaced already, 1 energy-saving lamp remain.

样例输入

5 4

3 10 5 2 7

10

5 1 4 8 7 2 3 6 4 7

样例输出

4 0

1 1

3 6

5 1

5 1

2 0

3 2

4 4

3 6

5 1

**题意**

城堡里有n个房间每个房间里有ki盏旧灯，Lpl每天购买m盏灯，他会按顺序，如果他的新灯>=房间的旧灯，他会拿新灯替换所有旧灯，直到不能替换，q个询问，每个询问输出两个数字分别为当前月有几个房间已经替换过了，还剩下几盏灯

**题解**

可以预处理出所有查询，每个查询循环1-n判断能否替换，显然是不行的

可以考虑每次找到可替换的最左边，显然可以用线段树维护区间最小值

**代码**

#include<bits/stdc++.h>

using namespace std; const int maxn=1e5+;

int minn[maxn<<];

void build(int l,int r,int rt)

{

if(l==r)

{

scanf("%d",&minn[rt]);

return;

}

int mid=(l+r)>>;

build(l,mid,rt<<);

build(mid+,r,rt<<|);

minn[rt]=min(minn[rt<<],minn[rt<<|]);

}

int query(int L,int R,int l,int r,int rt)

{

if(L<=l&&r<=R)

return minn[rt];

int mid=(l+r)>>,ans=1e9;

if(L<=mid)ans=min(ans,query(L,R,l,mid,rt<<));

if(R>mid)ans=min(ans,query(L,R,mid+,r,rt<<|));

return ans;

} int n,m,q;

int La,Fr,Left;

int f[maxn],r[maxn];

void update(int L,int R,int l,int r,int rt)

{

if(L>r||R<l)return;

if(L<=l&&r<=R&&minn[rt]>La)return;

if(l==r)

{

Fr++;

La-=minn[rt];

Left=l;

minn[rt]=0x3f3f3f3f;

return;

}

int mid=(l+r)>>;

if(L<=mid)update(L,R,l,mid,rt<<);

if(R>mid)update(L,R,mid+,r,rt<<|);

minn[rt]=min(minn[rt<<],minn[rt<<|]);

}

int main()

{

scanf("%d%d",&n,&m);

build(,n,); for(int i=;i<=;i++)

{

if(Fr==n)

{

f[i]=Fr;

r[i]=La;

continue;

}

La+=m;

Left=;

while(query(Left,n,,n,)<=La)update(Left,n,,n,);

f[i]=Fr;

r[i]=La;

} scanf("%d",&q);

for(int i=,x;i<q;i++)

{

scanf("%d",&x);

printf("%d %d\n",f[x],r[x]);

}

return ;

}

## 最新文章

- MVC5 网站开发之七 用户功能 3用户资料的修改和删除
- js计时器，点击开始计时，再点击停止
- Guava-Optional可空类型
- 【转载】VMware下LINUX的虚拟机增加磁盘空间
- BM25相关度打分公式
- NGINX(三)HASH表
- ubuntu 13.04 root权限设置方法详解
- 【转】java读写二进制文件的解决方法
- varnish屏蔽control+F5导致缓存失效
- day13-迭代器及生成器
- 视频流PS，PS封装H264
- 如何 通过 userAgent 区别微信小程序
- 模拟js中注册表单验证
- POJ 2976 3111（二分-最大化平均值）
- Hausdorff Distance(豪斯多夫距离)
- 高可用Hadoop平台－实战
- 并发编程>>并发级别（二）
- Hdu5181 numbers
- 纯css画三角形，勾等形状
- lightoj 1282 && uva 11029

## 热门文章

- 构建第一个maven工程
- TP中验证码的实现
- Python基础7- 流程控制之循环
- BZOJ-1305 dance跳舞 建图+最大流+二分判定
- LA 3295 (计数 容斥原理) Counting Triangles
- python 爬虫时遇到问题及解决
- bootstrap注意事项（八）一些辅助信息
- 创建txt格式文本日志
- MPLS VPN随堂笔记2
- BZOJ 3881: [Coci2015]Divljak [AC自动机 树链的并]
- 未能加载文件或程序集“System.Web.Mvc, Version=5.2.4.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35”或它的某一个依赖项
- linux swap空间的swappiness=0
- 总结Hibernate4.1+版本与Hibernate3.3+版本区别
- 以 BZOJ 2002 为例学习有根树LCT(Link-Cut Tree)
- Redis记录-Redis命令
- hadoop - hdfs 基础操作
- HDS推出HUS中端阵列 文件、块和对象统一存储
- Microsoft Azure
- ETL testing
- 试用log4jdbc