This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |