Submission #1255905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255905		biank	Radio Towers (IOI22_towers)	C++20	100 / 100	540 ms	36928 KiB

towers

#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

const int INF = 2e9 + 9;

struct PersistentSegTree {
    int n;
    vi st, l, r;
    PersistentSegTree(int _n) : n(_n), st(1, 0), l(1, 0), r(1, 0) {}
    int new_node(int u) {
        st.pb(st[u]);
        l.pb(l[u]);
        r.pb(r[u]);
        return sz(st) - 1;
    }
    int update(int pos, int toAdd, int lo, int hi, int node) {
        node = new_node(node);
        if (hi - lo == 1) {
            st[node] += toAdd;
            return node;
        }
        int mid = (lo + hi) / 2;
        if (pos < mid) {
            l[node] = update(pos, toAdd, lo, mid, l[node]);
        } else {
            r[node] = update(pos, toAdd, mid, hi, r[node]);
        }
        st[node] = st[l[node]] + st[r[node]];
        return node;
    }
    int update(int pos, int toAdd, int root) {
        return update(pos, toAdd, 0, n, root);
    }
    int query(int s, int e, int lo, int hi, int node) {
        if (e <= lo || hi <= s) {
            return 0;
        }
        if (s <= lo && hi <= e) {
            return st[node];
        }
        int mid = (lo + hi) / 2;
        return query(s, e, lo, mid, l[node]) +
                query(s, e, mid, hi, r[node]);
    }
    int query(int s, int e, int root) {
        return query(s, e, 0, n, root);
    }
    int findFirst(int s, int e, int lo, int hi, int node) {
        if (e <= lo || hi <= s || !st[node]) {
            return -1;
        }
        if (hi - lo == 1) {
            return lo;
        }
        int mid = (lo + hi) / 2;
        int k = findFirst(s, e, lo, mid, l[node]);
        if (k != -1) return k;
        return findFirst(s, e, mid, hi, r[node]);
    }
    int findFirst(int s, int e, int root) {
        return findFirst(s, e, 0, n, root);
    }
    int findLast(int s, int e, int lo, int hi, int node) {
        if (e <= lo || hi <= s || !st[node]) {
            return -1;
        }
        if (hi - lo == 1) {
            return lo;
        }
        int mid = (lo + hi) / 2;
        int k = findLast(s, e, mid, hi, r[node]);
        if (k != -1) return k;
        return findLast(s, e, lo, mid, l[node]);
    }
    int findLast(int s, int e, int root) {
        return findLast(s, e, 0, n, root);
    }
};

template<typename T>
struct SegTree {
    int n;
    vector<T> st;
    T neutr;
    SegTree() {}
    SegTree(vector<T> &a, T null) : n(sz(a)), st(2 * n), neutr(null) {
        forn(i, n) st[i + n] = a[i];
        dforsn(i, 1, n) st[i] = max(st[2 * i], st[2 * i + 1]);
    }
    T query(int l, int r) {
        T ans = neutr;
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l & 1) ans = max(ans, st[l++]);
            if (r & 1) ans = max(st[--r], ans);
        }
        return ans;
    }
};

struct Node {
    ll maxi = -INF, mini = INF, bestDiff1 = 0, bestDiff2 = 0;
};

Node merge(Node a, Node b) {
    Node c;
    c.maxi = max(a.maxi, b.maxi);
    c.mini = min(a.mini, b.mini);
    c.bestDiff1 = max({a.bestDiff1, b.bestDiff1, a.maxi - b.mini});
    c.bestDiff2 = max({a.bestDiff2, b.bestDiff2, b.maxi - a.mini});
    return c;
}

struct OtherSegTree {
    int n;
    vector<Node> st;
    OtherSegTree() {}
    OtherSegTree(vi &h) {
        n = 1;
        while (n < sz(h)) n *= 2;
        st.resize(2 * n);
        forn(i, sz(h)) st[i + n].maxi = st[i + n].mini = h[i];
        dforsn(i, 1, n) st[i] = merge(st[2 * i], st[2 * i + 1]);
    }
    Node query(int l, int r) {
        Node leftRes, rightRes;
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l & 1) leftRes = merge(leftRes, st[l++]);
            if (r & 1) rightRes = merge(st[--r], rightRes);
        }
        return merge(leftRes, rightRes);
    }
};

int n;
vi h, val;
vi l, r;
vi Ds, roots;
PersistentSegTree persistent_segtree(0);
SegTree<ii> minH;
OtherSegTree segtree;

void init(int N, vi H) {
    n = N, h = H;
    l.resize(N), r.resize(N);
    forn(i, N) {
        int j = i - 1;
        while (j >= 0 && H[j] > H[i]) j = l[j];
        l[i] = j;
    }
    dforn(i, N) {
        int j = i + 1;
        while (j < N && H[j] > H[i]) j = r[j];
        r[i] = j;
    }
    
    segtree = OtherSegTree(H);
    vi negR(N);
    vector<ii> negH(N);
    forn(i, N) negH[i] = {-h[i], i};
    minH = SegTree<ii>(negH, ii{-INF, -1});
    vi a(N + 2, INF);
    forn(i, N) a[i + 1] = H[i];
    SegTree st(a, -INF);
    val.resize(N);
    forn(i, N) val[i] = min(st.query(l[i] + 1, i + 2), st.query(i + 1, r[i] + 2)) - H[i];
    vi order(N);
    iota(all(order), 0);
    sort(all(order), [&](const int &lhs, const int &rhs) {
        return val[lhs] > val[rhs];
    });
    Ds = val;
    Ds.pb(INF);
    sort(all(Ds));
    Ds.erase(unique(all(Ds)), end(Ds));
    reverse(all(Ds));
    int i = 0;
    int root = 0;
    persistent_segtree = PersistentSegTree(n);
    for (int D : Ds) {
        while (i < N && val[order[i]] >= D) {
            root = persistent_segtree.update(order[i++], 1, root);
        }
        roots.pb(root);
    }
}

int max_towers(int L, int R, int D) {
    int lo = 0, hi = sz(Ds);
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (D <= Ds[mid]) lo = mid;
        else hi = mid;
    }
    int cant = persistent_segtree.query(L, R + 1, roots[lo]);
    int leftmost = persistent_segtree.findFirst(L, R + 1, roots[lo]);
    int rightmost = persistent_segtree.findLast(L, R + 1, roots[lo]);
    if (cant == 0) {
        leftmost = rightmost = minH.query(L, R + 1).snd;
        assert(leftmost != -1);
        cant++;
    }
    if (segtree.query(L, leftmost).bestDiff2 >= D) cant++;
    if (segtree.query(rightmost + 1, R + 1).bestDiff1 >= D) cant++;
    return cant;
}

• 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