Submission #851021

#	Time	Username	Problem	Language	Result	Execution time	Memory
851021		arbuzick	Advertisement 2 (JOI23_ho_t2)	C++17	59 / 100	2089 ms	343748 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

constexpr int R = 1 << 19, inf = 2e9 + 7;

set<pair<int, int>> tree[R * 2][2];

void add(int pos, int tp, pair<int, int> val) {
    for (pos += R; pos > 0; pos /= 2) {
        tree[pos][tp].insert(val);
    }
}

void del(int pos, int tp, pair<int, int> val) {
    for (pos += R; pos > 0; pos /= 2) {
        tree[pos][tp].erase(val);
    }
}

pair<int, int> get_min(int l, int r, int tp) {
    l += R;
    r += R;
    pair<int, int> ans = {inf, -1};
    while (l < r) {
        if (l & 1) {
            if (!tree[l][tp].empty()) {
                ans = min(ans, *tree[l][tp].begin());
            }
            l++;
        }
        if (r & 1) {
            --r;
            if (!tree[r][tp].empty()) {
                ans = min(ans, *tree[r][tp].begin());
            }
        }
        l >>= 1;
        r >>= 1;
    }
    return ans;
}

pair<int, int> get_max(int l, int r, int tp) {
    l += R;
    r += R;
    pair<int, int> ans = {-inf, -1};
    while (l < r) {
        if (l & 1) {
            if (!tree[l][tp].empty()) {
                ans = max(ans, *tree[l][tp].rbegin());
            }
            l++;
        }
        if (r & 1) {
            --r;
            if (!tree[r][tp].empty()) {
                ans = max(ans, *tree[r][tp].rbegin());
            }
        }
        l >>= 1;
        r >>= 1;
    }
    return ans;
}

void solve() {
    int n;
    cin >> n;
    vector<int> x(n), e(n);
    vector<pair<int, int>> ord;
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> e[i];
    }
    vector<int> b = x;
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    for (int i = 0; i < n; ++i) {
        x[i] = lower_bound(b.begin(), b.end(), x[i]) - b.begin();
        add(x[i], 0, {b[x[i]] - e[i], i});
        add(x[i], 1, {b[x[i]] + e[i], i});
        ord.emplace_back(e[i], i);
    }
    sort(ord.rbegin(), ord.rend());
    int ans = 0;
    vector<int> used(n);
    for (auto [val, ind] : ord) {
        if (used[ind]) {
            continue;
        }
        used[ind] = 1;
        ans++;
        del(x[ind], 0, {b[x[ind]] - e[ind], ind});
        del(x[ind], 1, {b[x[ind]] + e[ind], ind});
        while (true) {
            auto p = get_max(0, x[ind] + 1, 0);
            if (p.second == -1 || p.first < b[x[ind]] - e[ind]) {
                break;
            }
            used[p.second] = 1;
            del(x[p.second], 0, {b[x[p.second]] - e[p.second], p.second});
            del(x[p.second], 1, {b[x[p.second]] + e[p.second], p.second});
        }
        while (true) {
            auto p = get_min(x[ind], R, 1);
            if (p.second == -1 || p.first > b[x[ind]] + e[ind]) {
                break;
            }
            used[p.second] = 1;
            del(x[p.second], 0, {b[x[p.second]] - e[p.second], p.second});
            del(x[p.second], 1, {b[x[p.second]] + e[p.second], p.second});
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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