Submission #1346628

#TimeUsernameProblemLanguageResultExecution timeMemory
1346628killerzaluuAdvertisement 2 (JOI23_ho_t2)C++20
100 / 100
102 ms31732 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<long long,long long>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }

    sort(a.begin(), a.end());

    vector<pair<long long,long long>> b;
    for (int i = 0; i < n; ) {
        int j = i;
        long long x = a[i].first;
        long long mx = a[i].second;
        while (j < n && a[j].first == x) {
            mx = max(mx, a[j].second);
            j++;
        }
        b.push_back({x, mx});
        i = j;
    }

    int m = (int)b.size();

    vector<long long> x(m + 2), e(m + 2);
    for (int i = 1; i <= m; i++) {
        x[i] = b[i - 1].first;
        e[i] = b[i - 1].second;
    }

    const long long NEG = -(1LL << 60);

    vector<long long> pref(m + 2, NEG), suff(m + 2, NEG);

    for (int i = 1; i <= m; i++) {
        pref[i] = max(pref[i - 1], x[i] + e[i]);
    }

    for (int i = m; i >= 1; i--) {
        suff[i] = max(suff[i + 1], e[i] - x[i]);
    }

    int ans = 0;
    for (int i = 1; i <= m; i++) {
        bool bad = false;

        if (pref[i - 1] >= x[i] + e[i]) bad = true;
        if (suff[i + 1] >= e[i] - x[i]) bad = true;

        if (!bad) ans++;
    }

    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...