Submission #311790

#	Time	Username	Problem	Language	Result	Execution time	Memory
311790		keta_tsimakuridze	Interval Collection (CCO20_day2problem2)	C++14	25 / 25	4668 ms	222824 KiB

Main

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=1e6+5, Mx=1e9+5, Mn=-1e9+5;
int n,x,y;
multiset<int>l,r,Sl[N],Sr[N];
pair<pair<int,int>,int> tree[4*N];
char c;
void build(int u,int l,int r){
        tree[u].f.f=Mn;
		tree[u].f.s=Mx;
		tree[u].s=Mx-Mn;
	if(l==r) {
		return;
	}
	int mid=(l+r)/2;
	build(2*u,l,mid);
	build(2*u+1,mid+1,r);
}
void update(int u,int ind,int l,int r,int val,int type){
	// f.f - lefti
	if(l>ind || r<ind) return;
	if(l==r) {
		if(type==0){
			tree[u].f.s=val;
		}
		else tree[u].f.f=val;
		tree[u].s=tree[u].f.s-tree[u].f.f;
		return;
	}
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val,type);
	update(2*u+1,ind,mid+1,r,val,type);
	tree[u].f.f=max(tree[2*u].f.f,tree[2*u+1].f.f);
	tree[u].f.s=min(tree[2*u].f.s,tree[2*u+1].f.s);
	tree[u].s=min(tree[2*u].s,min(tree[2*u+1].s,tree[2*u+1].f.s-tree[2*u].f.f));
}
int main(){
	cin>>n;
	build(1,1,N);
	//cout<<"+"<<endl;
	for(int k=1;k<=n;k++){
		cin>>c>>x>>y;
		//cout<<c<<" "<<x<<" "<<y<<endl;
		if(c=='R'){
		l.erase(l.find(x));
		r.erase(r.find(y));
		Sr[x].erase(Sr[x].find(y));
		Sl[y].erase(Sl[y].find(x));
		if(Sr[x].size())
			update(1,x,1,N,*Sr[x].begin(),0);
		else update(1,x,1,N,Mx,0);
		
		if(Sl[y].size())
			update(1,y,1,N,*(--Sl[y].end()),1);
		else update(1,y,1,N,Mn,1);
		}
		else {
		l.insert(x);
		r.insert(y);
		Sr[x].insert(y);
		Sl[y].insert(x);
		update(1,x,1,N,*Sr[x].begin(),0);
		update(1,y,1,N,*(--Sl[y].end()),1);
		}
		if(*(--l.end())<=*r.begin()){
			cout<<*Sr[*(--l.end())].begin()-*(--Sl[*r.begin()].end())<<endl;
		}
		else cout<<tree[1].s<<endl;
		
	}
}

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