Submission #628795

#	Time	Username	Problem	Language	Result	Execution time	Memory
628795		imeimi2000	Radio Towers (IOI22_towers)	C++17	0 / 100	1420 ms	138672 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int inf = 1e9 + 5;
struct MaxSeg {
    int seg[1 << 18];
    MaxSeg() {
        fill(seg, seg + (1 << 18), -inf);
    }
    void update(int i, int s, int e, int x, int v) {
        if (s == e) {
            seg[i] = v;
            return;
        }
        int m = (s + e) / 2;
        if (x <= m) update(i + i, s, m, x, v);
        else update(i + i + 1, m + 1, e, x, v);
        seg[i] = max(seg[i + i], seg[i + i + 1]);
    }
    int query(int i, int s, int e, int x, int y) const {
        if (e < x || y < s) return -inf;
        if (x <= s && e <= y) return seg[i];
        int m = (s + e) / 2;
        return max(query(i + i, s, m, x, y), query(i + i + 1, m + 1, e, x, y));
    }
    int find(int i, int s, int e, int x, int v) const {
        if (x < s) return 0;
        if (e <= x && seg[i] <= v) return 0;
        if (s == e) return s;
        int m = (s + e) / 2;
        int r = find(i + i + 1, m + 1, e, x, v);
        if (r) return r;
        return find(i + i, s, m, x, v);
    }
};

struct Pst {
    struct Node {
        int L, R, S;
    };
    int root;
    vector<Node> node;
    vector<int> snapshots;
    Pst() {
        root = 0;
        node.push_back(Node { 0, 0, 0 });
        snapshots.push_back(0);
    }
    int update(int i, int s, int e, int x, int v) {
        int j = node.size();
        node.push_back(node[i]);
        node[j].S += v;
        if (s < e) {
            int m = (s + e) / 2;
            if (x <= m) node[j].L = update(node[j].L, s, m, x, v);
            else node[j].R = update(node[j].R, m + 1, e, x, v);
        }
        return j;
    }
    void update(int x, int v) {
        root = update(1, 1, inf, x, v);
    }
    int query(int i, int s, int e, int x, int y) const {
        if (!i || e < x || y < s) return 0;
        if (x <= s && e <= y) return node[i].S;
        int m = (s + e) / 2;
        return query(node[i].L, s, m, x, y) + query(node[i].R, m + 1, e, x, y);
    }
    int query(int t, int x, int y) const {
        return query(snapshots[t], 1, inf, x, y);
    }
    void snapshot() {
        snapshots.push_back(root);
    }
};

int n;
struct Tower {
    MaxSeg min_seg, max_seg;
    int maxD[100005];
    vector<pii> D[100005];
    Pst pst;
    void init(vector<int> H) {
        H.insert(H.begin(), inf);
        for (int i = 1; i <= n; ++i) {
            min_seg.update(1, 1, n, i, -H[i]);
            max_seg.update(1, 1, n, i, H[i]);
            D[i].emplace_back(0, 0);
        }
        vector<int> R = { 0, 1 };
        pst.snapshot();
        for (int i = 2; i <= n; ++i) {
            int poped = 0;
            while (H[R.back()] < H[i]) {
                R.pop_back();
                ++poped;
            }
            if (!poped) {
                int p = min_seg.find(1, 1, n, i, -H[i]);
                if (p) {
                    int p = *upper_bound(R.begin(), R.end(), p);
                    if (maxD[p]) pst.update(maxD[p], -1);
                    maxD[p] = H[p] - H[i];
                    D[p].emplace_back(i, maxD[p]);
                    pst.update(maxD[p], 1);
                }
            }
            R.push_back(i);
            pst.snapshot();
        }
    }
    int query(int m, int r, int d) const {
        int ans = pst.query(r, d, inf) - pst.query(m, d, inf);
        int mn = -min_seg.query(1, 1, n, m + 1, r);
        int p = min_seg.find(1, 1, n, m, -mn);
        // printf("p_ans = %d, mn = %d, p = %d\n", ans, mn, p);
        if (!p) return ans;
        int mx = max_seg.query(1, 1, n, p, r);
        int x = max_seg.find(1, 1, n, r, mx - 1);
        int pd = prev(upper_bound(D[x].begin(), D[x].end(), pii(m, inf)))->second;
        if (d <= pd) ++ans;
        int nd = mx - mn;
        if (d <= nd) --ans;
        // printf("n_ans = %d, mx = %d, x = %d\n", ans, mx, x);
        return ans;
    }
} L, R;

void init(int N, vector<int> H) {
    n = N;
    L.init(H);
    reverse(H.begin(), H.end());
    R.init(H);
}

int max_towers(int L, int R, int D) {
    ++L;
    ++R;
    int V = ::L.max_seg.query(1, 1, n, L, R);
    int M = ::L.max_seg.find(1, 1, n, R, V - 1);
    return ::L.query(M, R, D) + ::R.query(n + 1 - M, n + 1 - L, D) + (V - D >= -::L.min_seg.query(1, 1, n, L, M - 1) && V - D >= -::L.min_seg.query(1, 1, n, M + 1, R)) + 1;
}

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