问题 B: 乌鸦喝水
时间限制: 2 Sec 内存限制: 128 MB
题目描述
【题目背景】
一只乌鸦在自娱自乐，它在面前放了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
Sample Output
9
【数据范围】
100%的数据，0＜n≤100000，0＜m≤100000，0＜x≤2000000000，0＜Wi≤2000000000，0＜Ai≤200。
设 num=(X-w[i])/a[i]这个就是当前的缸还能撑住水位下降几次。
又因为虽然他能撑住这么多次，但是乌鸦飞到他上面前还要过i-1个缸，又要喝水。
所以num[i]=(X-w[i])/a[i]-i+1;这样就可以了。但是如果前面的一个缸不会被喝水，那么后面就被多减了，其实可以找到第一个会被干掉的点，删掉，再给他后面的区间+1，就又解决了。耳罩第一个不符合的点只要维护个区间最小，二分一下。
所以每一轮只要删掉所有不满足的，给后面加回来，让ans+=根节点上符合的个数就好了。
跑得贼快。
#pragma GCC optimize("O3")
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100005
#define mod 10000000007ll
#define ll long long
using namespace std;
struct tree{int l,r;ll h,lz,sum;}t[N*4];
int n,m;ll ans,X,w[N],a[N],zz[N];
ll min(ll x,ll y){return x<y?x:y;}
void down(int x)
{
ll l=t[x].lz;t[x].lz=0;
t[x*2].h+=l;t[x*2].lz+=l;
t[x*2+1].h+=l;t[x*2+1].lz+=l;
}
void build(int l,int r,int x)
{
t[x].l=l;t[x].r=r;
if(l==r)
{
t[x].h=(X-w[l])/a[l]-l+1;
t[x].sum=1;
return;
}
int mid=l+r>>1;
build(l,mid,x*2);build(mid+1,r,x*2+1);
t[x].sum=t[x*2].sum+t[x*2+1].sum;
t[x].h=min(t[x*2].h,t[x*2+1].h);
}
void c(int l,int r,int x)
{
if(l>r)return ;
if(t[x].l>=l&&t[x].r<=r)
{
t[x].h++;t[x].lz++;
return;
}
if(t[x].lz)down(x);
int mid=t[x].l+t[x].r>>1;
if(l<=mid)c(l,r,x*2);
if(r>mid)c(l,r,x*2+1);
t[x].sum=t[x*2].sum+t[x*2+1].sum;
t[x].h=min(t[x*2].h,t[x*2+1].h);
}
void del(int l,int x)
{
if(t[x].l==t[x].r)
{
t[x].h=mod;t[x].sum=0;
return;
}
int mid=t[x].l+t[x].r>>1;
if(t[x].lz)down(x);
if(l<=mid)del(l,x*2);
else del(l,x*2+1);
t[x].sum=t[x*2].sum+t[x*2+1].sum;
t[x].h=min(t[x*2].h,t[x*2+1].h);
}
int q(ll k,int x)
{
if(t[x].l==t[x].r)return t[x].l;
if(t[x].lz)down(x);
if(t[x*2].h<k)return q(k,x*2);
else return q(k,x*2+1);
}
int main()
{
//freopen("hh.txt","r",stdin);
// freopen(".out","w",stdout);
scanf("%d%d%lld",&n,&m,&X);
for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
build(1,n,1);
while(m--)
{
while(t[1].h<ans)
{
//cout<<t[1].h<<endl;
int k=q(ans,1);
del(k,1);c(k+1,n,1);
}
ans+=t[1].sum;
if(!t[1].sum)break;
}
printf("%lld
",ans);
}