Submission #312018

#TimeUsernameProblemLanguageResultExecution timeMemory
312018wildturtleInterval Collection (CCO20_day2problem2)C++14
22 / 25
4364 ms478288 KiB
#include<bits/stdc++.h> using namespace std; long long a,b,t,n,tree[4000006],treeL[4000006],treeR[4000006]; multiset <long long> stl,str,msl[1000006],msr[1000006]; 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]=1e17; else treeR[node]=*msr[idx].tavi; } else { if(msl[idx].empty()) treeL[node]=-1e17; 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<=4000000;i++) { tree[i]=2*1e17; treeL[i]=-1e17; treeR[i]=1e17; } 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+1,b,0); update(1,1,1e6+1,a,1); } else { stl.erase(stl.find(a)); str.erase(str.find(b)); msl[b].erase(a); msr[a].erase(b); update(1,1,1e6+1,b,0); update(1,1,1e6+1,a,1); } if(*(stl.bolo)<=*(str.tavi)) { //kveta //cout<<"*"; cout<<*(msr[*(stl.bolo)].tavi)-*(msl[*(str.tavi)].bolo)<<endl; } else { cout<<tree[1]<<endl; } } } /* 5 A 1 5 A 2 7 A 4 6 A 6 8 R 4 6*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...