Submission #1248016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248016		mickey080929	Radio Towers (IOI22_towers)	C++17	56 / 100	658 ms	36112 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 Fenwick{
    vector<int> tree;
    void init(int n) {
        tree.assign(n+1, 0);
    }
    void upd(int i, int v, int n) {
        i ++;
        while (i <= n) {
            tree[i] += v;
            i += i & -i;
        }
    }
    int sum(int i) {
        i ++;
        int ret = 0;
        while
    }
}*/

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 state[100010], stateS[100010];
int cand[100010];
int D;
int par[100010];
int Lpar[100010][20], Rpar[100010][20];
int Lsum[100010], Rsum[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;
        if (max(lmn, rmn) > H[pv] - D) {
            state[pv] = 1;
        }
        else cand[pv] = 1;
    }
    return pv;
}

void init(int _N, vector<int> _H) {
    N = _N;
    H = _H;
}

void dfs(int x) {
    if (Lch[x] != -1) {
        int y = Lch[x];
        Lsum[y] = Lsum[x] + cand[x];
        Rsum[y] = Rsum[x];
        Lpar[y][0] = x;
        Rpar[y][0] = Rpar[x][0];
        dfs(y);
    }
    if (Rch[x] != -1) {
        int y = Rch[x];
        Lsum[y] = Lsum[x];
        Rsum[y] = Rsum[x] + cand[x];
        Lpar[y][0] = Lpar[x][0];
        Rpar[y][0] = x;
        dfs(y);
    }
}

map<int,int> mp;

void my_init(int d) {
    D = d;
    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];
    stateS[0] = state[0];
    for (int i=1; i<N; i++) {
        leafS[i] = leafS[i-1] + leaf[i];
        stateS[i] = stateS[i-1] + state[i];
    }
    Lpar[root][0] = Rpar[root][0] = -1;
    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];
        }
    }
}

bool flag = false;
int max_towers(int l, int r, int d) {
    if (!flag) {
        my_init(d);
        flag = true;
    }
    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 = stateS[r] - (l ? stateS[l-1] : 0);
    sub -= state[l] + state[r];
    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 += Lsum[l] - Lsum[x];
    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 += Rsum[r] - Rsum[x];
    if (state[pv] == 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: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 0 / 17
• Subtask 6: 19 / 19
• Subtask 7: 0 / 23