Submission #1248025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248025		mickey080929	Radio Towers (IOI22_towers)	C++17	100 / 100	747 ms	103252 KiB

towers

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

using namespace std;

const int inf = 1e9;

struct SegmentTree{
    vector<pair<int,int>> tree;
    void init(int n, vector<int> a) {
        int sz = 1 << __lg(n) + 2;
        tree.resize(sz);
        build(1, 0, n-1, a);
    }
    void build(int node, int s, int e, vector<int> &a) {
        if (s == e) {
            tree[node] = {a[s], s};
            return;
        }
        int mid = s + e >> 1;
        build(node*2, s, mid, a);
        build(node*2+1, mid+1, e, a);
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }
    pair<int,int> query(int node, int s, int e, int l, int r) {
        if (l > e || s > r) return {-inf, -1};
        if (l <= s && e <= r) return tree[node];
        int mid = s + e >> 1;
        return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
    }
};

struct Node{
    int l, r, val;
};

struct PersistentSegmentTree{
    vector<Node> tree;
    void init() {
        tree.clear();
        tree.push_back({-1, -1, 0});
    }
    void update(int pnode, int node, int s, int e, int tar, int val) {
        tree[node].val = val;
        if (pnode != -1) tree[node].val += tree[pnode].val;
        if (s == e) {    
            return;
        }
        int mid = s + e >> 1;
        if (tar <= mid) {
            tree[node].l = tree.size();
            tree.push_back({-1, -1, 0});
            if (pnode != -1) tree[node].r = tree[pnode].r;
            update((pnode == -1 ? -1 : tree[pnode].l), tree[node].l, s, mid, tar, val);
        }
        else {
            tree[node].r = tree.size();
            tree.push_back({-1, -1, 0});
            if (pnode != -1) tree[node].l = tree[pnode].l;
            update((pnode == -1 ? -1 : tree[pnode].r), tree[node].r, mid+1, e, tar, val);
        }
    }
    int query(int node, int s, int e, int l, int r) {
        if (node == -1 || l > e || s > r) return 0;
        if (l <= s && e <= r) return tree[node].val;
        int mid = s + e >> 1;
        return query(tree[node].l, s, mid, l, r) + query(tree[node].r, mid+1, e, l, r);
    }
    int newroot() {
        tree.push_back({-1, -1, 0});
        return tree.size() - 1;
    }
};

SegmentTree seg, minseg;
int Lch[100010], Rch[100010], L[100010], R[100010];
vector<int> H;
int N;
int root;
int leaf[100010], leafS[100010];
int cand[100010];
int D;
int par[100010];
int Lpar[100010][20], Rpar[100010][20];
int diff[100010];

PersistentSegmentTree PST, PSTL, PSTR;
int head[100010], headL[100010], headR[100010];

int makeTree(int l, int r) {
    if (l > r) return -1;
    pair<int,int> ret = seg.query(1, 0, N-1, l, r);
    int pv = ret.second;
    L[pv] = l; R[pv] = r;
    Lch[pv] = makeTree(l, pv-1);
    Rch[pv] = makeTree(pv+1, r);
    if (Lch[pv] != -1) par[Lch[pv]] = pv;
    if (Rch[pv] != -1) par[Rch[pv]] = pv;
    if (Lch[pv] == -1 && Rch[pv] == -1) {
        leaf[pv] = 1;
    }
    else if (Lch[pv] != -1 && Rch[pv] != -1) {
        int lmn = -minseg.query(1, 0, N-1, l, pv-1).first;
        int rmn = -minseg.query(1, 0, N-1, pv+1, r).first;
        diff[pv] = H[pv] - max(lmn, rmn);
    }
    return pv;
}

void dfs(int x) {
    if (Lch[x] != -1) {
        int y = Lch[x];
        if (Lch[x] != -1 && Rch[x] != -1) {
            headL[y] = PSTL.newroot();
            PSTL.update(headL[x], headL[y], 0, inf, diff[x], 1);
        }
        else {
            headL[y] = headL[x];
        }
        headR[y] = headR[x];
        Lpar[y][0] = x;
        Rpar[y][0] = Rpar[x][0];
        dfs(y);
    }
    if (Rch[x] != -1) {
        int y = Rch[x];
        headL[y] = headL[x];
        if (Lch[x] != -1 && Rch[x] != -1) {
            headR[y] = PSTR.newroot();
            PSTR.update(headR[x], headR[y], 0, inf, diff[x], 1);
        }
        else {
            headR[y] = headR[x];
        }
        Lpar[y][0] = Lpar[x][0];
        Rpar[y][0] = x;
        dfs(y);
    }
}

void init(int _N, vector<int> _H) {
    N = _N;
    H = _H;
    seg.init(N, H);
    vector<int> t = H;
    for (auto &x : t) x = -x;
    minseg.init(N, t);
    root = makeTree(0, N-1);
    par[root] = -1;
    leafS[0] = leaf[0];
    for (int i=1; i<N; i++) {
        leafS[i] = leafS[i-1] + leaf[i];
    }
    PST.init();
    int prv = 0;
    for (int i=0; i<N; i++) {
        if (Lch[i] != -1 && Rch[i] != -1) {
            head[i] = PST.newroot();
            PST.update(prv, head[i], 0, inf, diff[i], 1);
        }
        else {
            head[i] = prv;
        }
        prv = head[i];
    }
    Lpar[root][0] = Rpar[root][0] = -1;
    PSTL.init();
    PSTR.init();
    headL[root] = headR[root] = 0;
    dfs(root);
    for (int lv=1; lv<=19; lv++) {
        for (int i=0; i<N; i++) {
            if (Lpar[i][lv-1] == -1) Lpar[i][lv] = -1;
            else Lpar[i][lv] = Lpar[Lpar[i][lv-1]][lv-1];
            if (Rpar[i][lv-1] == -1) Rpar[i][lv] = -1;
            else Rpar[i][lv] = Rpar[Rpar[i][lv-1]][lv-1];
        }
    }
}

int state(int i, int d) {
    return Lch[i] != -1 && Rch[i] != -1 && diff[i] < d;
}

int max_towers(int l, int r, int d) {
    if (l == r) return 1;
    int ans = leafS[r] - (l ? leafS[l-1] : 0);
    if (!leaf[l] && Rch[l] == -1) ans ++;
    if (!leaf[r] && Lch[r] == -1) ans ++;
    int sub = PST.query(head[r], 0, inf, 0, d-1) - (l ? PST.query(head[l-1], 0, inf, 0, d-1) : 0);
    sub -= state(l, d) + state(r, d);
    pair<int,int> ret = seg.query(1, 0, N-1, l, r);
    int mx = ret.first, pv = ret.second;
    int x = l;
    for (int lv=19; lv>=0; lv--) {
        if (Lpar[x][lv] != -1 && H[Lpar[x][lv]] < mx) {
            int p = Lpar[x][lv];
            int mn = -minseg.query(1, 0, N-1, l, p-1).first;
            if (mn > H[p] - d) x = p;
        }
    }
    sub += PSTL.query(headL[l], 0, inf, d, inf) - PSTL.query(headL[x], 0, inf, d, inf);
    x = r;
    for (int lv=19; lv>=0; lv--) {
        if (Rpar[x][lv] != -1 && H[Rpar[x][lv]] < mx) {
            int p = Rpar[x][lv];
            int mn = -minseg.query(1, 0, N-1, p+1, r).first;
            if (mn > H[p] - d) x = p;
        }
    }
    sub += PSTR.query(headR[r], 0, inf, d, inf) - PSTR.query(headR[x], 0, inf, d, inf);
    if (state(pv, d) == 0 && l != pv && r != pv) {
        int mnL = -minseg.query(1, 0, N-1, l, pv-1).first;
        int mnR = -minseg.query(1, 0, N-1, pv+1, r).first;
        if (max(mnL, mnR) > mx - d) sub ++;
    }
    return ans - sub;
}

• 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