Submission #1185460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185460		PieArmy	Segments (IZhO18_segments)	C++20	100 / 100	2206 ms	4296 KiB

segments

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

const int K=1900;

int n,m,t;
int lef[200023],rig[200023];
int id,lastans=0;
int p[200023],pl[200023],pr[200023];
vector<int>v;

void build(){
	sort(p,p+m,[&](const int &x,const int &y){
		return (rig[x]-lef[x])<(rig[y]-lef[y]);
	});
	for(int i=0;i<m;i++){
		pr[i]=pl[i]=p[i];
	}
	for(int i=0;i<m;i+=K){
		sort(pl+i,pl+min(i+K,m),[&](const int &x,const int &y){
			return lef[x]>lef[y];
		});
		sort(pr+i,pr+min(i+K,m),[&](const int &x,const int &y){
			return rig[x]<rig[y];
		});
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>t;
	iota(p,p+n,1);
	for(int ii=1;ii<=n;ii++){
		if(ii%K==0){
			m=id;
			for(int x:v){
				lef[x]=-1;
				rig[x]=-2;
			}
			v.clear();
			build();
		}
		int c;cin>>c;
		if(c==1){
			id++;
			cin>>lef[id]>>rig[id];
			lef[id]^=(t*lastans);
			rig[id]^=(t*lastans);
			if(lef[id]>rig[id])swap(lef[id],rig[id]);
		}
		else if(c==2){
			int x;cin>>x;
			v.pb(x);
		}
		else{
			int l,r,k;cin>>l>>r>>k;
			l^=(t*lastans);
			r^=(t*lastans);
			if(l>r)swap(l,r);
			lastans=0;
			for(int i=m+1;i<=id;i++){
				if(min(r,rig[i])-max(l,lef[i])<k-1)continue;
				lastans++;
			}
			for(int i:v){
				if(min(r,rig[i])-max(l,lef[i])<k-1)continue;
				lastans--;
			}
			for(int i=0;i<m;i+=K){
				int j=min(i+K-1,m-1);
				if(rig[p[j]]-lef[p[j]]<k-1)continue;
				if(rig[p[i]]-lef[p[i]]<k-1){
					for(int o=i;o<=j;o++){
						if(min(r,rig[p[o]])-max(l,lef[p[o]])<k-1)continue;
						lastans++;
					}
					continue;
				}
				lastans+=j-i+1;
				int le=i,ri=j+1;
				while(le<ri){
					int mi=(le+ri)/2;
					if(lef[pl[mi]]>r-k+1)le=mi+1;
					else ri=mi;
				}
				lastans-=le-i;
				le=i;ri=j+1;
				while(le<ri){
					int mi=(le+ri)/2;
					if(rig[pr[mi]]<l+k-1)le=mi+1;
					else ri=mi;
				}
				lastans-=le-i;
			}
			cout<<lastans<<endl;
		}
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 25 / 25