Submission #1343799

#TimeUsernameProblemLanguageResultExecution timeMemory
1343799nguyenkhangninh99Advertisement 2 (JOI23_ho_t2)C++20
0 / 100
1 ms344 KiB

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve(){
    int n; cin >> n;

    vector<array<int, 2>> a(n + 1); //0 = x, 1 = e;
    for(int i = 1; i <= n; i++) cin >> a[i][0] >> a[i][1];
    
    sort(a.begin() + 1, a.end());
    stack<int> s;

    vector<int> deg(n + 1), del(n + 1); //xét i < j

    for(int i = 1; i < n; i++) del[i] = (a[i] == a[i + 1]);
    for(int i = 1; i <= n; i++){ //xi - xj >= ei - ej -> xi - ei >= xj - ej
        if(del[i]) continue;
        while(s.size() && a[s.top()][0] - a[s.top()][1] >= a[i][0] - a[i][1]){
            deg[s.top()]++;
            s.pop();
        }
        s.push(i);
    }

    while(s.size()) s.pop();
    for(int i = n; i >= 1; i--){ //xj - xi >= ei - ej -> xj + ej >= xi + ei
        if(del[i]) continue;
        while(s.size() && a[s.top()][0] + a[s.top()][1] <= a[i][0] + a[i][1]){
            deg[s.top()]++;
            s.pop();
        }
        s.push(i);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) ans += (deg[i] == 0);
    cout << ans;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    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...