Submission #851025

#	Time	Username	Problem	Language	Result	Execution time	Memory
851025		arbuzick	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	1197 ms	200464 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];

pair<int, int> mn[R * 2][2], mx[R * 2][2];

void build() {
    for (int i = 1; i < R * 2; ++i) {
        for (int tp = 0; tp < 2; ++tp) {
            mn[i][tp] = {inf, -1};
            mx[i][tp] = {-inf, -1};
        }
    }
}

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

void del(int pos, int tp, pair<int, int> val) {
    pos += R;
    tree[pos][tp].erase(val);
    if (tree[pos][tp].empty()) {
        mn[pos][tp] = {inf, -1};
        mx[pos][tp] = {-inf, -1};
    } else {
        mn[pos][tp] = *tree[pos][tp].begin();
        mx[pos][tp] = *tree[pos][tp].rbegin();
    }
    for (pos /= 2; pos > 0; pos /= 2) {
        mn[pos][tp] = min(mn[pos * 2][tp], mn[pos * 2 + 1][tp]);
        mx[pos][tp] = max(mx[pos * 2][tp], mx[pos * 2 + 1][tp]);
    }
}

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) {
            ans = min(ans, mn[l][tp]);
            l++;
        }
        if (r & 1) {
            --r;
            ans = min(ans, mn[r][tp]);
        }
        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) {
            ans = max(ans, mx[l][tp]);
            l++;
        }
        if (r & 1) {
            --r;
            ans = max(ans, mx[r][tp]);
        }
        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];
    }
    build();
    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: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31