Submission #938553

#TimeUsernameProblemLanguageResultExecution timeMemory
938553the_coding_poohAdvertisement 2 (JOI23_ho_t2)C++14
100 / 100
1523 ms96108 KiB
#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

const int SIZE = 5e5 + 5;

int N;

int X[SIZE], E[SIZE];

int innode[SIZE];

map<int, pair<int, int>> mp;

#define fs first
#define sc second

vector<int> disX;

int main(){
    cin >> N;

    for (int i = 0; i < N;i++){
        cin >> X[i] >> E[i];
        if(mp[X[i]].fs < E[i]){
            mp[X[i]].fs = E[i];
            mp[X[i]].sc = 1;
        }
    }
    
    for(auto i:mp){
        disX.push_back(i.fs);
    }
    
    N = disX.size();

    set<int> XmE, XpE;

    for (int i = 0; i < N;i++){
        if(XpE.lower_bound(disX[i] + mp[disX[i]].fs) != XpE.end()){
            innode[i]++;
        }
        XpE.insert(disX[i] + mp[disX[i]].fs);
    }

    for (int i = N - 1; i >= 0;i--){
        if(XmE.upper_bound(disX[i] - mp[disX[i]].fs) != XmE.begin()){
            innode[i]++;
        }
        XmE.insert(disX[i] - mp[disX[i]].fs);
    }
    

    int cnt = 0;
    for (int i = 0; i < N;i++){
        //cout << innode[i] << '\n';
        if(!innode[i])
            cnt += mp[disX[i]].sc;
    }
    cout << cnt << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...