oj.uz

Submission #312139

# Submission time Handle Problem Language Result Execution time Memory
312139 2020-10-12T13:02:33 Z wildturtle Interval Collection (CCO20_day2problem2) C++14
0 / 25
 7000 ms 283256 KB 
#include<bits/stdc++.h>
using namespace std;
long long a,b,t,tree[4000035],treeL[4000035],treeR[4000035];
multiset <long long> stl,str,msl[1000005],msr[1000005];
char ch;
#define tavi begin()
#define bolo rbegin()
void update(long long node,long long L,long long R,long long idx,long long mxare) {
	if(idx<L || R<idx) return;
	if(L==R) {
		if(mxare) { if(msr[idx].empty()) treeR[node]=1e9; else treeR[node]=*msr[idx].tavi; }
		else { if(msl[idx].empty()) treeL[node]=-1e9; else treeL[node]=*msl[idx].bolo; }
		tree[node]=treeR[node]-treeL[node];
		return;
	}
	update(2*node,L,(L+R)/2,idx,mxare);
	update(2*node+1,(L+R)/2+1,R,idx,mxare);
	tree[node]=min(min(tree[2*node],tree[2*node+1]),treeR[2*node+1]-treeL[2*node]);
	treeL[node]=max(treeL[2*node],treeL[2*node+1]);
	treeR[node]=min(treeR[2*node],treeR[2*node+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; treeL[i]=-1e9; treeR[i]=1e9;
    }
	cin>>t;
	while(t--) {
		cin>>ch>>a>>b;
		if(ch=='A') {
			stl.insert(a);
			str.insert(b);
			msl[b].insert(a);
			msr[a].insert(b);
			update(1,1,1e6+5,b,0);
			update(1,1,1e6+5,a,1);
		}
		else {
			stl.erase(stl.find(a));
			str.erase(str.find(b));
			msl[b].erase(msl[b].find(a));
			msr[a].erase(msl[a].find(b));
			update(1,1,1e6+5,b,0);
			update(1,1,1e6+5,a,1);
		}
		if(*(stl.bolo)<=*(str.tavi)) cout<<*(msr[*(stl.bolo)].tavi)-*(msl[*(str.tavi)].bolo)<<endl;
		else cout<<tree[1]<<endl;
	}
}

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7062 ms 188280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7062 ms 188280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7062 ms 188280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 226252 KB Output is correct
2 Correct 962 ms 226424 KB Output is correct
3 Correct 1768 ms 264220 KB Output is correct
4 Correct 1825 ms 264224 KB Output is correct
5 Correct 2170 ms 283256 KB Output is correct
6 Correct 2225 ms 283236 KB Output is correct
7 Execution timed out 7081 ms 188204 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7062 ms 188280 KB Time limit exceeded
2 Halted 0 ms 0 KB -