Submission #936749

#	Time	Username	Problem	Language	Result	Execution time	Memory
936749		kitlix	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	951 ms	73572 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INF = 1e18;

struct NodeMax {
    long long seg_max;

    static NodeMax merge(NodeMax a, NodeMax b) { return {max(a.seg_max, b.seg_max)}; }

    static NodeMax zero_el() { return {-INF}; }
};

template <class Node>
struct SegTree {
    vector<Node> t;

    int n, h = 1;

    SegTree(const int& sz) : SegTree(vector<Node>(sz, Node::zero_el())) {}

    SegTree(vector<Node> in) {
        n = in.size();
        while (1 << h < n)
            h += 1;
        t.resize(1 << (h + 1), Node::zero_el());
        for (int i = (1 << h); i < (1 << h) + n; ++i)
            t[i] = in[i - (1 << h)];
        for (int i = (1 << h) - 1; i > 0; --i)
            t[i] = Node::merge(t[i << 1], t[(i << 1) | 1]);
    }

    void upd(int v, int v_l, int v_r, int i, Node val) {
        if (i < v_l || i >= v_r)
            return;
        if (v_l + 1 == v_r) {
            t[v] = val;
            return;
        }
        int v_m = (v_l + v_r) / 2;
        upd((v << 1), v_l, v_m, i, val);
        upd(((v << 1) | 1), v_m, v_r, i, val);
        t[v] = Node::merge(t[v << 1], t[(v << 1) | 1]);
    }

    void upd(int i, Node val) { upd(1, 0, (1 << h), i, val); }

    Node get(int v, int v_l, int v_r, int l, int r) {
        if (v_l >= r || v_r <= l)
            return Node::zero_el();
        if (l <= v_l && v_r <= r)
            return t[v];
        int v_m = (v_l + v_r) / 2;
        return Node::merge(get((v << 1), v_l, v_m, l, r), get(((v << 1) | 1), v_m, v_r, l, r));
    }

    Node get(int l, int r) { return get(1, 0, (1 << h), l, r); }

    Node get_by_id(int i) { return t[(1 << h) + i - 1]; };
};

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    vector<int> xs;
    for (auto& [ei, xi] : a) {
        cin >> xi >> ei;
        xs.push_back(xi);
    }
    sort(xs.begin(), xs.end());
    xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
    map<int, int> xcomp;
    for (int i = 0; i < xs.size(); ++i)
        xcomp[xs[i]] = i;
    for (auto& [ei, xi] : a)
        xi = xcomp[xi];
    sort(a.begin(), a.end(), greater<>());
    SegTree<NodeMax> preft(xs.size()), sufft(xs.size());
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int prefmx = preft.get(0, a[i].second + 1).seg_max;
        if (prefmx >= a[i].first + xs[a[i].second])
            continue;
        int suffmx = sufft.get(a[i].second, xs.size()).seg_max;
        if (suffmx >= a[i].first - xs[a[i].second])
            continue;
        ans += 1;
        preft.upd(a[i].second, {a[i].first + xs[a[i].second]});
        sufft.upd(a[i].second, {a[i].first - xs[a[i].second]});
    }
    cout << ans;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:77:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < xs.size(); ++i)
      |                     ~~^~~~~~~~~~~

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