数据过水
查看原帖
数据过水
748437
AirQwQ楼主2024/10/21 09:12

场上乱写了个最坏 O(nq)O(nq) 的做法,结果拿了 80pts,只有性质 D 没过。

主要代码:

	SegmentTree T(a);
	while(q--){
		int op,x,y;cin>>op>>x>>y;
		if(op==1) T.update(x,y),a[x]+=y;
		else {
			if(T.queryMax(x,y)>w1)cout<<"tetris"<<endl;
			else{
				int l=x,r=y,suml=T.querySum(x,min(y,x+c2-1)),sumr=T.querySum(max(x,y-c2+1),y);
				while(suml<=w2&&l+c2-1<=y){
					suml-=a[l],suml+=a[l+c2];
					l++;	
				}
				while(sumr<=w2&&r-c2+1>=x){
					sumr-=a[r],sumr+=a[r-c2];
					r--;	
				}
				if(suml<=w2||sumr<=w2){
					cout<<"cont"<<endl;
				}
				else{
					if(r-l+1>c1||T.querySum(l,r)>w1) cout<<"tetris"<<endl;
					else cout<<"cont"<<endl;
				}
			} 
		}
	}
2024/10/21 09:12
加载中...