Submission #310847

#	Time	Username	Problem	Language	Result	Execution time	Memory
310847		mosiashvililuka	Interval Collection (CCO20_day2problem2)	C++14	25 / 25	4266 ms	335516 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N=2200009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,za,seg[N],seg2[N],seg3[N];
char ch;
multiset <int> lf[N],rg[N],mn,mx;
void up(int q){
	if(q==0) return;
	if(seg[q*2]==-1||seg[q*2+1]==-1){
		seg[q]=max(seg[q*2],seg[q*2+1]);
	}else{
		seg[q]=min(seg[q*2],seg[q*2+1]);
	}
	seg2[q]=max(seg2[q*2],seg2[q*2+1]);
	if(seg3[q*2]==-1||seg3[q*2+1]==-1){
		seg3[q]=max(seg3[q*2],seg3[q*2+1]);
	}else{
		seg3[q]=min(seg3[q*2],seg3[q*2+1]);
	}
	int qw=seg3[q*2+1]-seg2[q*2];
	if(seg3[q*2+1]!=-1&&seg2[q*2]!=-1){
		if(seg[q]>qw||seg[q]==-1) seg[q]=qw;
	}
	up(q/2);
}
void upd(int q){
	multiset <int>::iterator it,tt,zit,ztt;
	if(lf[q].size()==0||rg[q].size()==0){
		seg[q+za-1]=-1;
	}else{
		it=lf[q].end();it--;
		tt=rg[q].begin();
		seg[q+za-1]=(*tt)-(*it);
	}
	if(lf[q].size()==0){
		seg2[q+za-1]=-1;
	}else{
		it=lf[q].end();it--;
		seg2[q+za-1]=(*it);
	}
	if(rg[q].size()==0){
		seg3[q+za-1]=-1;
	}else{
		it=rg[q].begin();
		seg3[q+za-1]=(*it);
	}
	up((q+za-1)/2);
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>tes;
	za=1;
	while(za<1000000) za*=2;
	for(i=1; i<=za*2; i++){
		seg[i]=-1;
		seg2[i]=seg3[i]=-1;
	}
	for(t=1; t<=tes; t++){
		cin>>ch>>c>>d;
		if(ch=='A'){
			lf[d].insert(c);
			rg[c].insert(d);
			mn.insert(d);
			mx.insert(c);
		}else{
			lf[d].erase(lf[d].lower_bound(c));
			rg[c].erase(rg[c].lower_bound(d));
			mn.erase(mn.lower_bound(d));
			mx.erase(mx.lower_bound(c));
		}
		upd(c);
		upd(d);
		multiset <int>::iterator it,tt,zit,ztt;
		it=mn.begin();
		tt=mx.end();tt--;
		if((*tt)<(*it)){
			c=(*tt);d=(*it);
			zit=lf[d].end();zit--;
			ztt=rg[c].begin();
			cout<<(*ztt)-(*zit)<<endl;
		}else{
			cout<<seg[1]<<endl;
		}
	}
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 4 / 4
• Subtask 5: 3 / 3