Submission #1057181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057181		tvladm2009	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	132 ms	74780 KiB

prison

#include <bits/stdc++.h>
 
 
using namespace std;
 
 
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
 
int n, d, t;
vector<int> a, b, low;
 
 
struct SparseTable {
    int n;
    vector<vector<int>> rmq;
    vector<int> lg;
 
 
    SparseTable(int N, vector<int> a) {
        n = N;
        rmq.assign(21, vector<int>(n + 1, 0));
        for (int i = 1; i <= n; i += 1) {
            rmq[0][i] = a[i];
        }
        lg.resize(n + 1);
        for (int i = 2; i <= n; i += 1) {
            lg[i] = lg[i / 2] + 1;
        }
        for (int h = 1; h < 21; h += 1) {
            for (int i = 1; i + (1 << h) - 1 <= n; i += 1) {
                rmq[h][i] = min(rmq[h - 1][i], rmq[h - 1][i + (1 << (h - 1))]);
            }
        }
    }
 
 
    int get_min(int l, int r) {
        assert(l <= r);
        int p = lg[r - l + 1];
        return min(rmq[p][l], rmq[p][r - (1 << p) + 1]);
    }
};
 
 
struct Node {
    int mx;
    int pos;
};
 
 
Node join(Node a, Node b) {
    Node c;
    c = (a.mx > b.mx ? a : b);
    return c;
}
 
 
vector<Node> segt;
vector<int> lazy;
 
 
void push(int v, int tl, int tr) {
    if (tl < tr) {
        lazy[2 * v] += lazy[v];
        lazy[2 * v + 1] += lazy[v];
    }
    segt[v].mx += lazy[v];
    lazy[v] = 0;
}
 
 
void build(int v, int tl, int tr) {
    if (tl == tr) {
        segt[v] = {0, tl};
    } else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        segt[v] = join(segt[2 * v], segt[2 * v + 1]);
    }
}
 
 
void add(int v, int tl, int tr, int l, int r, int x) {
    push(v, tl, tr);
    if (l > tr || r < tl) {
        return;
    }
    if (l <= tl && tr <= r) {
        lazy[v] += x;
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    add(2 * v, tl, tm, l, r, x);
    add(2 * v + 1, tm + 1, tr, l, r, x);
    segt[v] = join(segt[2 * v], segt[2 * v + 1]);
}
 
int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> d >> t;
    a.resize(n + 1);
    b.resize(n + 1);
    for (int i = 1; i <= n; i += 1) {
        cin >> a[i];
        b[i] = a[i] - i;
    }
    SparseTable rmq(n, b);
    low.resize(n + 1);
    for (int i = 1; i <= n; i += 1) {
        if (a[i] <= t) {
            low[i] = -1;
            continue;
        }
        int l = 1, r = i - 1, sol = i;
        while (l <= r) {
            int m = (l + r) / 2;
            if (rmq.get_min(m, i) > t - i) {
                sol = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        sol -= 1;
        low[i] = max(1, sol);
    }
    segt.resize(4 * n + 1);
    lazy.resize(4 * n + 1);
    build(1, 1, n);
    for (int i = 2; i <= n; i += 1) {
        if (low[i] != -1) {
            add(1, 1, n, low[i], i - 1, +1);
        }
    }
    vector<int> seen(n + 1, 0);
    int ans = n;
    for (int step = 1; step <= d; step += 1) {
        int p = segt[1].pos;
        ans -= segt[1].mx;
        // dumb
        for (int i = p + 1; i <= n; i += 1) {
            if (seen[i] == 0 && low[i] != -1 && low[i] <= p) {
                seen[i] = 1;
                add(1, 1, n, low[i], i - 1, -1);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20