Submission #951087

#	Time	Username	Problem	Language	Result	Execution time	Memory
951087		peterandvoi	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	572 ms	49296 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    int n;
    cin >> n;
    vector<int> x(n), e(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> e[i];
    }
    auto vx = x;
    auto ve = e;
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    sort(ve.begin(), ve.end());
    ve.erase(unique(ve.begin(), ve.end()), ve.end());
    for (int i = 0; i < n; ++i) {
        x[i] = lower_bound(vx.begin(), vx.end(), x[i]) - vx.begin();
        e[i] = lower_bound(ve.begin(), ve.end(), e[i]) - ve.begin();
    }
    vector<vector<int>> g((int) ve.size());
    for (int i = 0; i < n; ++i) {
        g[e[i]].emplace_back(i);
    }
    int m = (int) vx.size();
    const int INF = (int) 1e9;
    vector<int> sum(m, -INF), dif(m, INF);
    set<int> s;
    auto cover = [&](int i) {
        if (!s.size()) {
            return false;
        }
        int X = vx[x[i]];
        int E = ve[e[i]];
        auto it = s.lower_bound(x[i]);
        if (it != s.end()) {
            int r = *it;
            if (dif[r] <= X - E) {
                return true;
            }
        }
        if (it != s.begin()) {
            int l = *prev(it);
            if (X + E <= sum[l]) {
                return true;
            }
        }
        return false;
    };
    auto ins = [&](int i) {
        int X = vx[x[i]];
        int E = ve[e[i]];
        dif[x[i]] = min(dif[x[i]], X - E);
        sum[x[i]] = max(sum[x[i]], X + E);
        s.erase(x[i]);
        if (s.size()) {
            auto it = s.lower_bound(x[i]);
            if (it != s.end()) {
                sum[*it] = max(sum[*it], sum[x[i]]);
            }
            if (it != s.begin()) {
                int l = *prev(it);
                dif[l] = min(dif[l], dif[x[i]]);
            }
        }
        s.insert(x[i]);
    };
    int res = 0;
    for (int i = (int) g.size() - 1; ~i; --i) {
        for (int j : g[i]) {
            if (!cover(j)) {
                res++;
                ins(j);
            }
        }
    }
    cout << res;
}

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