Submission #891577

#TimeUsernameProblemLanguageResultExecution timeMemory
8915771075508020060209tcInterval Collection (CCO20_day2problem2)C++14
0 / 25
7006 ms808 KiB
#pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; #define int long long int Q; multiset<pair<int,int>>mst; int n; pair<int,int>ar[500005]; pair<int,int>interset(pair<int,int>a,pair<int,int>b){ pair<int,int>pr; pr.first=max(a.first,b.first); pr.second=min(a.second,b.second); return pr; } bool cmp(pair<int,int>i,pair<int,int>j){ if(i.second<j.second){return 1;} return 0; } int slv(int st,int d){ pair<int,int>pr={1,1e9}; for(int i=1;i<=n;i++){ if(ar[i].first<st){continue;} pr=interset(pr,ar[i]); if(max(pr.second-pr.first,0ll)<=d){ return ar[i].second-st; } } return 1e18; } void solve(){ n=0; pair<int,int>pr={1,1e9}; for(auto it=mst.begin();it!=mst.end();it++){ ar[++n]=(*it); pr=interset(pr,ar[n]); } int ans=1e18; sort(ar+1,ar+n+1); int d=max(pr.second-pr.first,0ll); for(int i=1;i<=n;i++){ ans=min(slv(ar[i].first,d),ans); } cout<<ans<<"\n"; } signed main(){ cin>>Q; while(Q--){ char typ; cin>>typ; int l;int r; cin>>l>>r; if(typ=='A'){ mst.insert({l,r}); }else{ mst.erase(mst.find({l,r})); } solve(); } }
#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...