Submission #1054915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054915		shiomusubi496	Radio Towers (IOI22_towers)	C++17	100 / 100	1238 ms	201288 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

constexpr ll inf = 1e18;

template<class M>
class SegmentTree {
    using T = typename M::T;
    int n;
    vector<T> dat;

public:
    SegmentTree() = default;
    SegmentTree(int n_, T x) {
        n = 1;
        while (n < n_) n *= 2;
        dat.assign(2 * n, x);
    }
    SegmentTree(vector<T> a) {
        n = 1;
        while (n < a.size()) n *= 2;
        dat.assign(2 * n, M::id());
        rep (i, a.size()) dat[i + n] = a[i];
        rrep2 (i, 1, n) dat[i] = M::op(dat[2 * i], dat[2 * i + 1]);
    }
    void set(int k, T x) {
        k += n;
        dat[k] = x;
        while (k > 1) {
            k /= 2;
            dat[k] = M::op(dat[2 * k], dat[2 * k + 1]);
        }
    }
    void apply(int k, T x) { set(k, M::op(dat[k + n], x)); }
    T prod(int l, int r) const {
        l += n; r += n;
        T lsm = M::id(), rsm = M::id();
        while (l < r) {
            if (l & 1) lsm = M::op(lsm, dat[l++]);
            if (r & 1) rsm = M::op(dat[--r], rsm);
            l >>= 1; r >>= 1;
        }
        return M::op(lsm, rsm);
    }
    T all_prod() const { return dat[1]; }
    T get(int k) const { return dat[k + n]; }
};

template<class M>
class PersistentSegmentTree {
    using T = typename M::T;
    int n;

public:
    struct Node;
    using node_ptr = Node*;
    struct Node {
        T val;
        node_ptr l, r;
        Node(T val_ = M::id(), node_ptr l_ = nullptr, node_ptr r_ = nullptr) : val(val_), l(l_), r(r_) {}
    };

private:
    node_ptr root;

public:
    PersistentSegmentTree() = default;
    void init(int n_, T x = M::id()) {
        n = 1;
        while (n < n_) n *= 2;
        vector<node_ptr> nodes(n * 2);
        rep (i, 2 * n) nodes[i] = new Node();
        rep (i, n_) nodes[i + n]->val = x;
        rrep2 (i, 1, n) nodes[i]->val = M::op(nodes[i * 2]->val, nodes[i * 2 + 1]->val);
        rep2 (i, 1, n) nodes[i]->l = nodes[i * 2], nodes[i]->r = nodes[i * 2 + 1];
        root = nodes[1];
    }

private:
    node_ptr set_(node_ptr p, int k, int bt, T x) {
        if (bt == 0) return new Node(x, p->l, p->r);
        if (k & bt) {
            auto ptr = set_(p->r, k, bt / 2, x);
            return new Node(M::op(p->l->val, ptr->val), p->l, ptr);
        }
        else {
            auto ptr = set_(p->l, k, bt / 2, x);
            return new Node(M::op(ptr->val, p->r->val), ptr, p->r);
        }
    }

public:
    void set(int k, T x) {
        root = set_(root, k, n / 2, x);
    }

private:
    T prod_(node_ptr p, int l, int r, int a, int b) const {
        if (r <= a || b <= l) return M::id();
        if (a <= l && r <= b) return p->val;
        return M::op(prod_(p->l, l, (l + r) / 2, a, b), prod_(p->r, (l + r) / 2, r, a, b));
    }

public:
    T prod(node_ptr ptr, int l, int r) const {
        return prod_(ptr, 0, n, l, r);
    }
    T prod(int l, int r) const { return prod(root, l, r); }
    T all_prod(node_ptr ptr) const { return ptr->val; }
    T all_prod() const { return all_prod(root); }
    node_ptr get_root() const { return root; }
};

struct Max {
    using T = ll;
    static T op(T a, T b) { return max(a, b); }
    static T id() { return -inf; }
};

struct Min {
    using T = ll;
    static T op(T a, T b) { return min(a, b); }
    static T id() { return inf; }
};

struct Sum {
    using T = ll;
    static T op(T a, T b) { return a + b; }
    static T id() { return 0; }
};

struct Monoid {
    using T = tuple<ll, ll, ll>;
    static T op(T a, T b) {
        auto [a1, a2, a3] = a;
        auto [b1, b2, b3] = b;
        return {a1 + b1, min(a2, b2), max(a3, b3)};
    }
    static T id() { return {0, inf, -inf}; }
};

int N;
vector<int> H, Hs;

PersistentSegmentTree<Monoid> seg1, seg2;
SegmentTree<Min> rmq;

using node_ptr = PersistentSegmentTree<Monoid>::node_ptr;

vector<node_ptr> ptr1, ptr2;
vector<ll> stamps;

void init(int N_, std::vector<int> H_) {
    N = N_; H = H_;
    Hs = H;
    stamps = {};
    ptr1 = ptr2 = {};
    sort(all(Hs));
    Hs.erase(unique(all(Hs)), Hs.end());
    rep (i, N) H[i] = lower_bound(all(Hs), H[i]) - Hs.begin();

    rmq = SegmentTree<Min>(N, inf);
    rep (i, N) rmq.set(i, H[i]);

    seg1.init(N);
    seg2.init(N);
    rep (i, N) {
        if ((i == 0 || H[i - 1] > H[i]) && (i == N - 1 || H[i] < H[i + 1])) seg1.set(i, {1, i, i});
    }
    rep (i, N) {
        if ((i == 0 || H[i - 1] < H[i]) && (i == N - 1 || H[i] > H[i + 1])) seg2.set(i, {1, i, i});
    }
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> que;
    rep (i, N) {
        if (get<0>(seg2.prod(i, i + 1)) == 1) {
            auto [s1, l1, r1] = seg1.prod(0, i);
            auto [s2, l2, r2] = seg1.prod(i + 1, N);
            ll t = -inf;
            if (s1 != 0) chmax(t, Hs[H[r1]]);
            if (s2 != 0) chmax(t, Hs[H[l2]]);
            que.emplace(Hs[H[i]] - t, i);
        }
    }
    while (!que.empty()) {
        auto [d, k] = que.top(); que.pop();
        // if (d >= D) break;
        stamps.push_back(d);
        ptr1.push_back(seg1.get_root());
        ptr2.push_back(seg2.get_root());
        if (get<0>(seg2.prod(k, k + 1)) == 0) continue;
        auto [s1, l1, r1] = seg1.prod(0, k);
        auto [s2, l2, r2] = seg1.prod(k + 1, N);
        {
            ll t = -inf;
            if (s1 != 0) chmax(t, Hs[H[r1]]);
            if (s2 != 0) chmax(t, Hs[H[l2]]);
            if (d != Hs[H[k]] - t) continue;
        }
        if (s1 == 0 && s2 == 0) continue;
        if (s1 == 0 || (s2 != 0 && H[r1] < H[l2])) {
            seg1.set(l2, {0, inf, -inf});
            seg2.set(k, {0, inf, -inf});
            auto [s, l, r] = seg2.prod(k + 1, N);
            if (s == 0) continue;
            auto [s3, l3, r3] = seg1.prod(l + 1, N);
            ll t = -inf;
            if (s1 != 0) chmax(t, Hs[H[r1]]);
            if (s3 != 0) chmax(t, Hs[H[l3]]);
            que.emplace(Hs[H[l]] - t, l);
        }
        else {
            seg1.set(r1, {0, inf, -inf});
            seg2.set(k, {0, inf, -inf});
            auto [s, l, r] = seg2.prod(0, k);
            if (s == 0) continue;
            auto [s3, l3, r3] = seg1.prod(0, r);
            ll t = -inf;
            if (s2 != 0) chmax(t, Hs[H[l2]]);
            if (s3 != 0) chmax(t, Hs[H[r3]]);
            que.emplace(Hs[H[r]] - t, r);
        }
    }
    int inf = 1.1e9;
    stamps.push_back(inf);
    ptr1.push_back(seg1.get_root());
    ptr2.push_back(seg2.get_root());
}

int max_towers(int L, int R, int D) {
    auto itr = lower_bound(all(stamps), D) - stamps.begin();
    ++R;
    auto [s, l, r] = seg2.prod(ptr2[itr], L, R);
    if (s == 0) return 1;
    int res = s - 1;
    if (l != L && Hs[rmq.prod(L, l)] + D <= Hs[H[l]]) ++res;
    if (r != R - 1 && Hs[rmq.prod(r + 1, R)] + D <= Hs[H[r]]) ++res;
    return max(res, 1);
}

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23