Submission #938553

#	Time	Username	Problem	Language	Result	Execution time	Memory
938553		the_coding_pooh	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	1523 ms	96108 KiB

Main

#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';
}

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