제출 #895940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895940		rockstar	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	436 ms	56460 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops,inline")
//#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2,fma,bmi2,abm,popcnt,mmx,tune=native")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define int ll
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

struct segment_tree {
    vector<int> tree;
    int n;

    segment_tree(int n) : n(n) {
        tree.resize(4 * n, -3e9);
    }

    int get(int v, int tl, int tr, int l, int r) {
        if (tr < l || r < tl)
            return -3e9;
        if (l <= tl && tr <= r)
            return tree[v];
        int tm = (tl + tr) / 2;
        return max(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
    }

    void upd(int v, int tl, int tr, int p, int x) {
        if (tl == tr) {
            tree[v] = x;
            return;
        }
        int tm = (tl + tr) / 2;
        if (tm >= p)
            upd(v * 2, tl, tm, p, x);
        else
            upd(v * 2 + 1, tm + 1, tr, p, x);
        tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
    }

    int get(int l, int r) {
        return get(1, 0, n - 1, l, r);
    }

    void upd(int p, int x) {
        upd(1, 0, n - 1, p, x);
    }
};

/*
 * e_i   e_j
 * x_i   x_j
 * e_i - e_j >= x_j - x_i
 * e_i + x_i >= x_j + e_j
 */

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> p(n);
    for (int i = 0; i < n; ++i)
        cin >> p[i].first >> p[i].second;
    sort(all(p));
    vector<array<int, 3>> q(n);
    for (int i = 0; i < n; ++i)
        q[i] = {p[i].second, i, p[i].first};
    sort(rall(q));
//    for (auto i : q)
//        cout << i[0] << ' ';
//    cout << '\n';
    segment_tree neg(n), pos(n);
    int res = 0;
    for (int i = 0; i < n; ++i) {
//        cout << "elem: " << q[i][2] << ' ' << q[i][0] << ' ' << q[i][1] << endl;
//        cout << pos.get(0, q[i][1] - 1) << ' ' << neg.get(q[i][1] + 1, n - 1) << '\n';
        if (pos.get(0, q[i][1] - 1) < q[i][0] + q[i][2] && neg.get(q[i][1] + 1, n - 1) < q[i][0] - q[i][2]) {
            ++res;
//            cout << "now\n";
        }
        neg.upd(q[i][1], q[i][0] - q[i][2]);
        pos.upd(q[i][1], q[i][0] + q[i][2]);
    }
    cout << res;
}


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

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