Submission #314232

#	Time	Username	Problem	Language	Result	Execution time	Memory
314232		tigicha	Interval Collection (CCO20_day2problem2)	C++14	25 / 25	4341 ms	285120 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long a, b, t, tree[4000035], tree1[4000035], tree2[4000035];
multiset <long long> st1, st2, s1[1000005], s2[1000005];
char c;
void update(long long p, long long l, long long r, long long k, bool x){
	if(k<l || r<k) return;
	if(l==r){
		if(x==1){
		       if(s2[k].empty()) tree2[p]=1e9;
		       else tree2[p]=*s2[k].begin();
		}
		else{
		       if(s1[k].empty()) tree1[p]=-1e9;
		       else tree1[p]=*s1[k].rbegin();
		}
		tree[p]=tree2[p]-tree1[p];
		return;
	}
	update(2*p, l, (l+r)/2, k, x);
	update(2*p+1, (l+r+1)/2, r, k, x);
	tree[p]=min(min(tree[2*p], tree[2*p+1]), tree2[2*p+1]-tree1[2*p]);
	tree1[p]=max(tree1[2*p], tree1[2*p+1]);
	tree2[p]=min(tree2[2*p], tree2[2*p+1]);
}
int main(){
       std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	for (long long i=1; i<=4000020; i++){
	       tree[i]=2*1e9;
	       tree1[i]=-1e9;
	       tree2[i]=1e9;
	}
	cin>>t;
	while(t--){
	       cin>>c>>a>>b;
		if(c=='A'){
			st1.insert(a);
			st2.insert(b);
			s1[b].insert(a);
			s2[a].insert(b);
			update(1, 1, 1e6+5, b, 0);
			update(1, 1, 1e6+5, a, 1);
		}
		else {
			st1.erase(st1.find(a));
			st2.erase(st2.find(b));
			s1[b].erase(s1[b].find(a));
			s2[a].erase(s2[a].find(b));
			update(1, 1, 1e6+5, b, 0);
			update(1, 1, 1e6+5, a, 1);
		}
		if(*(st1.rbegin())<=*(st2.begin())) cout<<*(s2[*(st1.rbegin())].begin())-*(s1[*(st2.begin())].rbegin())<<endl;
		else cout<<tree[1]<<endl;
	}
}

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