oj.uz

Submission #310767

# Submission time Handle Problem Language Result Execution time Memory
310767 2020-10-07T20:48:07 Z mosiashvililuka Interval Collection (CCO20_day2problem2) C++17
0 / 25
 2137 ms 334456 KB 
#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(qw>0){
		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
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 231672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 231672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 231672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 272892 KB Output is correct
2 Correct 936 ms 272760 KB Output is correct
3 Correct 1680 ms 313832 KB Output is correct
4 Correct 1727 ms 313720 KB Output is correct
5 Correct 2070 ms 334456 KB Output is correct
6 Correct 2137 ms 334328 KB Output is correct
7 Incorrect 2100 ms 242424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 231672 KB Output isn't correct
2 Halted 0 ms 0 KB -