제출 #628848

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
628848		imeimi2000	송신탑 (IOI22_towers)	C++17	17 / 100	1511 ms	146868 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) {
        if (x == 0) return;
        root = update(root, 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];
    int Lmin[100005];
    int Lpos[100005];
    int Lpar[20][100005];
    int V[100005];
    Pst pst;
    void init(vector<int> H) {
        H.insert(H.begin(), inf);
        for (int i = 1; i <= n; ++i) {
            V[i] = H[i];
            min_seg.update(1, 1, n, i, -H[i]);
            max_seg.update(1, 1, n, i, H[i]);
        }
        vector<int> R = { 0, 1 };
        vector<int> L;
        pst.snapshot();
        Lmin[0] = Lmin[1] = inf;
        for (int i = 2; i <= n; ++i) {
            int poped = 0;
            Lmin[i] = inf;
            while (H[R.back()] < H[i]) {
                Lmin[i] = min(Lmin[i], min(Lmin[R.back()], H[R.back()]));
                if (!L.empty() && L.back() == R.back()) L.pop_back();
                R.pop_back();
                ++poped;
            }
            if (!poped) {
                while (!L.empty()) {
                    int x = L.back();
                    pst.update(maxD[x], -1);
                    if (Lmin[x] < H[i]) {
                        maxD[x] = H[x] - H[i];
                        pst.update(maxD[x], 1);
                        break;
                    }
                    else {
                        maxD[x] = H[x] - Lmin[x];
                        pst.update(maxD[x], 1);
                    }
                    L.pop_back();
                }
            }
            else {
                if (!L.empty()) Lpar[0][i] = L.back();
                L.push_back(i);
            }
            Lpos[i] = L.empty() ? 0 : L.back();
            R.push_back(i);
            pst.snapshot();
        }
        for (int i = 1; i < 20; ++i) {
            for (int j = 1; j <= n; ++j) Lpar[i][j] = Lpar[i - 1][Lpar[i - 1][j]];
        }
    }
    int query(int m, int r, int d) const {
        // printf("m = %d, r = %d\n", m, r);
        if (m == r) return 0;
        int ans = pst.query(r, d, inf) - pst.query(m, d, inf);
        int mn = -min_seg.query(1, 1, n, m + 1, r);
        int x = Lpos[m];
        // printf("ans = %d\n", ans);
        if (!x) return ans;
        if (Lmin[x] + d <= V[x] && mn + d <= V[x]) --ans;
        // printf("ans = %d\n", ans);
        for (int i = 20; i--; ) {
            int p = Lpar[i][x];
            if (!p) continue;
            if (Lmin[p] + d <= V[p] && mn + d <= V[p]);
            else x = p, ans -= 1 << i;
        }
        // printf("ans = %d\n", ans);
        x = Lpos[m];
        for (int i = 20; i--; ) {
            int p = Lpar[i][x];
            int g = Lpar[0][p];
            if (!g) continue;
            if (Lmin[g] + d <= V[g] && Lmin[p] + d <= V[g]);
            else x = p, ans += 1 << i;
        }
        // printf("ans = %d\n", ans);
        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: 17 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23