Submission #954998

#TimeUsernameProblemLanguageResultExecution timeMemory
954998OtalpAdvertisement 2 (JOI23_ho_t2)C++14
100 / 100
600 ms39412 KiB
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second

int us[500100];


void solve(){
    int n;
    cin>>n;
    vector<pii> q;
    
    for(int i=1; i<=n; i++){
        int l, r;
        cin>>l>>r;
        q.pb({l, r});
    }
    sort(q.begin(), q.end());
    multiset<pii> d1, d2;
    
    for(int i=0; i<n; i++){
        d2.insert({q[i].ff + q[i].ss, i});
    }
    for(int i=0; i<n; i++){
        if(us[i]) continue;
        d2.erase(d2.find({q[i].ff + q[i].ss, i}));
        int x = q[i].ff - q[i].ss;
        while(d1.size() and (*d1.rbegin()).ff >= x){
            us[(*d1.rbegin()).ss] = 1;
            d1.erase(--(d1.end()));
        }
        x = q[i].ff + q[i].ss;
        while(d2.size() and (*d2.begin()).ff <= x){
            us[(*d2.begin()).ss] = 1;
            d2.erase(d2.begin());
        }
        d1.insert({q[i].ff - q[i].ss, i});
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        if(us[i] == 0) ans++;
    }
    cout<<ans;

}


int main(){
    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...