Submission #891578

#	Time	Username	Problem	Language	Result	Execution time	Memory
891578		1075508020060209tc	Interval Collection (CCO20_day2problem2)	C++14	3 / 25	7066 ms	1584 KiB

Main

#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,cmp);
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();
}



}

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