Submission #895754

#	Time	Username	Problem	Language	Result	Execution time	Memory
895754		rockstar	Advertisement 2 (JOI23_ho_t2)	C++17	0 / 100	55 ms	15700 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.begin(), a.end()

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 (tl <= l && r <= tr)
            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);
    }
};

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));
    segment_tree neg(n), pos(n);
    int res = 0;
    for (int i = 0; i < n; ++i) {
//        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;
        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: 0 / 10
• Subtask 2: 0 / 23
• Subtask 3: 0 / 36
• Subtask 4: 0 / 31