Submission #1057445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057445		tvladm2009	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2031 ms	329548 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]);
}
 
 
vector<int> segt_good;
 
 
void toggle(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        if (segt_good[v] == n + 1) {
            segt_good[v] = pos;
        } else {
            segt_good[v] = n + 1;
        }
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            toggle(2 * v, tl, tm, pos);
        } else {
            toggle(2 * v + 1, tm + 1, tr, pos);
        }
        int x = segt_good[2 * v];
        int y = segt_good[2 * v + 1];
        segt_good[v] = (low[x] < low[y] ? x : y);
    }
}
 
 
int get_next(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) {
        return n + 1;
    }
    if (l <= tl && tr <= r) {
        return segt_good[v];
    }
    int tm = (tl + tr) / 2;
    int x = get_next(2 * v, tl, tm, l, r);
    int y = get_next(2 * v + 1, tm + 1, tr, l, r);
    return low[x] < low[y] ? x : y;
}
 
 
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 + 2);
    for (int i = 1; i <= n; i += 1) {
        if (a[i] <= t) {
            low[i] = i;
            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] = sol;
    }
    low[n + 1] = n + 1;
    segt.resize(4 * n + 1);
    lazy.resize(4 * n + 1);
    segt_good.assign(4 * n + 1, n + 1);
    vector<bool> good(n + 1);
    build(1, 1, n - 1);
    int ans = 0;
    for (int i = 1; i <= n; i += 1) {
        good[i] = (low[i] > 0);
        if (low[i] > 0) {
            ans += 1;
            add(1, 1, n - 1, low[i], i, +1);
            toggle(1, 1, n, i);
        }
    }
    vector<int> seen(n + 1, 0);
    for (int step = 1; step <= d; step += 1) {
        int p = segt[1].pos;
        if (segt[1].mx == 0) {
			break;
        }
        while (true) {
            int x = get_next(1, 1, n, p + 1, n);
            if (x == n + 1) {
                break;
            }
            if (low[x] <= p) {
                good[x] = 0;
                ans -= 1;
                add(1, 1, n - 1, low[x], x, -1);
                toggle(1, 1, n, x);
            } else {
                break;
            }
        }
        // for (int i = p + 1; i <= n; i += 1) {
        //     if (good[i] == 1 && low[i] <= p) {
        //         seen[i] = 1;
        //         ans -= 1;
        //         good[i] = 0;
        //         add(1, 1, n - 1, low[i], i, -1);
        //     }
        // }
    }
    cout << ans << "\n";
    return 0;
}

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