「codecomb2096」lyz
Description
滑冰俱乐部初始有1->n号码溜冰鞋各k双，已知x号脚的人可以穿x->x+d号码的鞋子。现在有m次操作，每次两个数r、x，表示r号脚的人来了x个，x为负表示离开。对于每次操作，输出溜冰鞋是否足够。
Input
第一行四个整数n,m,k,d。
以下m行，每行一个操作。
Output
对于每一个询问，输出是否可行。若可行，输出TAK，反之，输出NIE。
Sample Input
4 4 2 1
1 3
2 3
3 3
2 -1
Sample Output
TAK
TAK
NIE
TAK
Hint
数据范围：
n<=200000,m<=500000,1<=k<=10^9,0<=d<=n,ri<=n-d
题解
如果某一段的需求和为sum，长度为len
而（len+d）* k >= sum 即为合法
把这式子倒腾一下
d * k >= sum – len * k
那么把线段树初值赋为 -k
就变为 d * k >= sum
问题转换为找一个最大子串和看它是否小等于d*k，线段树维护
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,K,d; ll lmx[800005],rmx[800005],mx[800005],sum[800005]; void modify(int k,int l,int r,int pos,int val) { if(l==r) { lmx[k]+=val;rmx[k]+=val;mx[k]+=val;sum[k]+=val; return; } int mid=(l+r)>>1; if(pos<=mid)modify(k<<1,l,mid,pos,val); else modify(k<<1|1,mid+1,r,pos,val); mx[k]=max(max(mx[k<<1],mx[k<<1|1]),rmx[k<<1]+lmx[k<<1|1]); sum[k]=sum[k<<1]+sum[k<<1|1]; lmx[k]=max(lmx[k<<1],sum[k<<1]+lmx[k<<1|1]); rmx[k]=max(rmx[k<<1|1],sum[k<<1|1]+rmx[k<<1]); } int main() { n=read();m=read();K=read();d=read(); for(int i=1;i<=n;i++)modify(1,1,n,i,-K); for(int i=1;i<=m;i++) { int r=read(),x=read(); modify(1,1,n,r,x); if(mx[1]<=(ll)d*K)puts("TAK"); else puts("NIE"); } return 0; } |
Subscribe
计数器 9774569
OI 课件=>
OI 课件=>