Submission #1248011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248011		mickey080929	Radio Towers (IOI22_towers)	C++17	23 / 100	4090 ms	20900 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 S[100010], leaf[100010];
int ans, D;

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 && Rch[pv] == -1) {
        ans ++;
    }
    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) {
            ans --;
        }
    }
    return pv;
}

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);
    S[0] = leaf[0];
    for (int i=1; i<N; i++) {
        S[i] = S[i-1] + leaf[i];
    }
}

int max_towers(int l, int r, int d) {
    D = d;
    ans = 0;
    makeTree(l, r);
    return ans;
}

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