Submission #1356167

#TimeUsernameProblemLanguageResultExecution timeMemory
1356167gayAdvertisement 2 (JOI23_ho_t2)C++20
100 / 100
1025 ms111036 KiB
#include <bits/stdc++.h>
#include <experimental/random>
#include <random>

//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;

using namespace std;

using ld = long double;
using ll = long long;

const ll INF = 1e18, MOD = 1e9 + 7;

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) {
        solve();
    }
}

struct seg_tree {
    vector<pair<ll, ll>> tree;
    void build(ll v, ll l, ll r, vector<ll>& a) {
        if (r - l == 1) {
            tree[v] = {a[l], l};
            return;
        }
        ll m = (l + r) / 2;
        build(2 * v, l, m, a);
        build(2 * v + 1, m, r, a);
        tree[v] = min(tree[2 * v], tree[2 * v + 1]);
    }
    void change(ll v, ll vl, ll vr, ll pos) {
        if (vr - vl == 1) {
            tree[v].first = INF;
            return;
        }
        ll m = (vl + vr) / 2;
        if (pos < m) {
            change(2 * v, vl, m, pos);
        } else {
            change(2 * v + 1, m, vr, pos);
        }
        tree[v] = min(tree[2 * v], tree[2 * v + 1]);
    }
    pair<ll, ll> get(ll v, ll vl, ll vr, ll l, ll r) {
        if (vl >= r || vr <= l) {
            return {INF, INF};
        }
        if (vl >= l && vr <= r) {
            return tree[v];
        }
        ll m = (vl + vr) / 2;
        return min(get(2 * v, vl, m, l, r), get(2 * v + 1, m, vr, l, r));
    }
};

void solve() {
    ll n; cin >> n;
    vector<pair<ll, ll>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end());
    set<pair<ll, ll>> hv;
    vector<ll> fir(n), sec(n);
    for (int i = 0; i < n; i++) {
        hv.insert({a[i].second, i});
        fir[i] = a[i].second - a[i].first;
        sec[i] = a[i].second + a[i].first;
    }
    seg_tree t1, t2;
    t1.tree.resize(4 * n), t2.tree.resize(4 * n);
    t1.build(1, 0, n, fir);
    t2.build(1, 0, n, sec);
    queue<ll> bfs;
    ll ans = 0;
    while (!hv.empty()) {
        if (bfs.empty()) {
            bfs.push(hv.rbegin()->second);
            t1.change(1, 0, n, bfs.back());
            t2.change(1, 0, n, bfs.back());
            hv.erase(--hv.end());
            ans++;
        }
        ll i = bfs.front();
        bfs.pop();
        while (true) {
            pair<ll, ll> cur = t1.get(1, 0, n, 0, i);
            if (cur.first > fir[i]) break;
            bfs.push(cur.second);
            t1.change(1, 0, n, cur.second);
            t2.change(1, 0, n, cur.second);
            hv.erase({a[cur.second].second, cur.second});
        }
        while (true) {
            pair<ll, ll> cur = t2.get(1, 0, n, i + 1, n);
            if (cur.first > sec[i]) break;
            bfs.push(cur.second);
            t1.change(1, 0, n, cur.second);
            t2.change(1, 0, n, cur.second);
            hv.erase({a[cur.second].second, cur.second});
        }
    }
    cout << ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...