Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 258 Solved: 97
Description
【题目背景】
一只乌鸦在自娱自乐，它在面前放了n个有魔力的水缸，水缸里装有无限的水。
【题目描述】
他准备从第1个水缸飞到第n个水缸，共m次。在飞过一个水缸的过程中，如果他能够得着水缸里的水，即水缸口到水面距离小于等于乌鸦能够得着的深度，那它就会喝水缸里的水。每喝一次水，所有水缸里的水位都会下降，第i个水缸里的水位会下降Ai，注意喝水是瞬间的，如果乌鸦刚好够得着，但喝完之后够不着，也视为喝到一次，水位也会相应的下降。
Input
共有3行。第一行有三个正整数n、m和x，用空格隔开。n表示水缸的数量，m表示乌鸦飞的次数，x表示乌鸦能够得着的深度。第二行，有n个用空格隔开的正整数，第i个数为第i个水缸中水缸口到水面的距离Wi。第三行，有n个用空格隔开的正整数，第i个为Ai。
Output
只有一行，这一行只有一个正整数，为这只乌鸦能喝到水的次数。
Sample Input
5 2 20
15 14 13 12 12
1 1 1 1 1
15 14 13 12 12
1 1 1 1 1
Sample Output
9
【数据范围】
100%的数据，0＜n≤100000，0＜m≤100000，0＜x≤2000000000，0＜Wi≤2000000000，0＜Ai≤200。
【数据范围】
100%的数据，0＜n≤100000，0＜m≤100000，0＜x≤2000000000，0＜Wi≤2000000000，0＜Ai≤200。
HINT
2016.7.8重设时限，未重测！
Source
脑洞题
应该算贪心+二分吧，思路挺神奇的
乌鸦喝水是“能喝的时候一定喝”的，所以和DP决策没关系。
直接模拟的复杂度为$O(nm)$
把每个水缸按照可以喝水的次数（即喝多少次水，水位下降到喝不到）由小到大排序，依次处理。
显然如果前面的水缸能喝n次，后面的水缸至少也能喝n次，这个性质十分有用。
由上面这句话可以推出：如果乌鸦从当前位置飞到队伍末会经过k个能喝的水缸，而当前水缸还能喝的次数x>=k，那么之后的水缸也不会在这一轮被喝空。
1、枚举每一个水缸开始（在枚举到该水缸的时候，前面剩余次数更小的水缸已经被喝完。或者可以理解为，舍弃前面的缸，贪心喝这个。）
2、用树状数组维护水缸的ID，查询从当前水缸的ID到（原先的）第n个水缸还有多少个能喝的水缸，如果当前缸的剩余次数>=剩余缸数，直接更新次数并跳到下一轮。
3、在数次2操作后，当前缸的剩余次数<=剩余缸数，此时在树状数组上二分“余数”，即喝到又一轮的某位置时，当前缸没水了。
4、将当前缸标为空，枚举下一个水缸。
表面看着复杂度高，实际上喝水的次数不会超过最多的那个缸能喝的次数（因为每次喝水都是所有缸水位一起下降的），同时，模拟操作的次数不会超过m（最多喝m轮），复杂度可以接受。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,X,N;
int t[mxn];
void add(int x,int v){
while(x<=N){t[x]+=v; x+=x&-x;}return;
}
int que(int x){
int res=;
while(x){res+=t[x];x-=x&-x;}
return res;
}
struct node{
int cnt,id;
bool operator < (node b)const{return cnt<b.cnt;}
}a[mxn];
int cir,last=;
int tot=;
int find(int x){
int res=last,l=last,r=n;
while(l<=r){
int mid=(l+r)>>;
if(que(mid)-que(last)<=x){
res=mid;
l=mid+;
}
else r=mid-;
}
return res;
}
void solve(){
for(int i=;i<=n;i++){
if(a[i].cnt<tot){
add(a[i].id,-);
continue;
}
while(cir<m && tot+(que(n)-que(last))<=a[i].cnt){
int tmp=que(n)-que(last);
cir++;//又能喝一轮
tot+=tmp;
last=;//从头开始
}
if(cir>=m)break;
int ed=find(a[i].cnt-tot);
// tot+=ed-last; //wrong
tot=a[i].cnt;
last=ed;
add(a[i].id,-);
}
return;
}
int main(){
int i,j,w;
N=n=read();m=read();X=read();
for(i=;i<=n;i++)
a[i].cnt=read(),a[i].id=i;
for(i=;i<=n;i++){
w=read();
a[i].cnt=(X-a[i].cnt)/w+;
}
w=;
for(i=;i<=n;i++)
if(a[i].cnt){
a[++w]=a[i];
add(a[i].id,);
}
n=w;
sort(a+,a+n+);
solve();
printf("%d\n",tot);
return ;
}