70分线段树MLE
查看原帖
70分线段树MLE
601009
S1746楼主2024/11/18 21:55

我把d和t从int变成long long后那3个点就从WA变成了MLE抽象

#include<bits/stdc++.h>
#define re register int
using namespace std;
int m,cnt;
long long a[400400],d,t;
inline void add(re l,re r,re x,re now,re num){
//	cout<<l<<" "<<r<<" "<<x<<" "<<now<<" "<<num<<endl;
	if(l==r){
		a[now]=num;
		return;
	}
	re mid=(l+r)/2;
	if(x>mid)add(mid+1,r,x,now*2+1,num);//右边 
	else add(l,mid,x,now*2,num);//左边 
	a[now]=max(a[now*2],a[now*2+1])%d;
}
inline long long find(re l,re r,re now,re lnow,re rnow){
//	cout<<l<<" "<<r<<" "<<now<<" "<<lnow<<" "<<rnow<<endl;
	long long ans=-(1<<62);
	if((l<=lnow&&rnow<=r)||lnow==rnow)return a[now];
	re mid=(lnow+rnow)/2;
	if(mid>=l)ans=max(ans,find(l,r,now*2,lnow,mid));//
	if(mid<r)ans=max(ans,find(l,r,now*2+1,mid+1,rnow));
	return ans;
}
int main(){
//	freopen("out.txt","w",stdout);
 cin>>m>>d;
 for(re i=1;i<=m;i++){
 	char x;long long y;
 	cin>>x>>y;
 	if(x=='Q'){
 //	cout<<t<<" "<<a[1]<<" "<<a[2]<<endl;
 	t=find(cnt-y+1,cnt,1,1,m)%d;
 	cout<<t<<endl;
	 //	printf("%lld\n",t=find(cnt-y+1,cnt,1,1,m)%d);
	 }
	 else{
	 	cnt++;
	 	add(1,m,cnt,1,(y+t)%d);
		 //cout<<(y+t)%d<<endl;
	 }
 }
  	return 0;
}
2024/11/18 21:55
加载中...