Submission #954998

#	Time	Username	Problem	Language	Result	Execution time	Memory
954998		Otalp	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	600 ms	39412 KiB

Main

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

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31