oj.uz

Submission #891577

# Submission time Handle Problem Language Result Execution time Memory
891577 2023-12-23T08:59:02 Z 1075508020060209tc Interval Collection (CCO20_day2problem2) C++14
0 / 25
 7000 ms 808 KB 
#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();
}



}

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 4.0

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

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -