Submission #672868

#	Time	Username	Problem	Language	Result	Execution time	Memory
672868		Kahou	The short shank; Redemption (BOI21_prison)	C++14	80 / 100	2067 ms	75068 KiB

prison

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int inf = 1e9 + 50;
const int N = 2e6 + 50;
int n, d, t[N], T, par[N];
int seg[N<<2], out[N<<2], lazy[N<<2];
bool vis[N];
int I[N];

void build(int c, int u=1, int tl=1, int tr=n) {
        if (tl == tr) {
                if (!c) seg[u] = inf;
                else seg[u] = 0, out[u] = tl;
                return;
        }
        int md = (tl+tr)/2;
        int lc = u<<1;
        int rc = u<<1|1;
        build(c, lc, tl, md), build(c, rc, md+1, tr);
        if (!c) seg[u] = min(seg[lc], seg[rc]);
        else seg[u] = max(seg[lc], seg[rc]), out[u] = (seg[lc] > seg[rc]? out[lc]: out[rc]);
}
void shift(int u) {
        int lc = u<<1;
        int rc = u<<1|1;
        seg[lc] += lazy[u];
        lazy[lc] += lazy[u];
        seg[rc] += lazy[u];
        lazy[rc] += lazy[u];
        lazy[u] = 0;
}
void upd(int c, int l, int r, int x, int u=1, int tl=1, int tr=n) {
        if (r < tl || tr < l) return;
        if (l <= tl && tr <= r) {
                if (!c) seg[u] = min(seg[u], x);
                else seg[u] += x, lazy[u] += x;
                return;
        }
        if (c) shift(u);
        int md = (tl+tr)/2;
        int lc = u<<1;
        int rc = u<<1|1;
        upd(c, l, r, x, lc, tl, md), upd(c, l, r, x, rc, md+1, tr);
        if (!c) seg[u] = min(seg[lc], seg[rc]);
        else seg[u] = max(seg[lc], seg[rc]), out[u] = (seg[lc] > seg[rc]? out[lc]: out[rc]);
}
int get(int x, int u=1, int tl=1, int tr=n) {
        if (seg[u] > x) return 0;
        if (tl == tr) return tl;
        int md = (tl+tr)/2;
        int lc = u<<1;
        int rc = u<<1|1;
        int out = get(x, rc, md+1, tr);
        if (!out) out = get(x, lc, tl, md);
        return out;
}

void solve() {
        cin >> n >> d >> T;
        for (int i = 1; i <= n; i++) {
                cin >> t[i];
        }
        build(0);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
                upd(0, i, i, t[i]-i);
                int x = get(T-i)+1;
                if (x > i) continue;
                if (x <= 1) {
                        ans++;
                        continue;
                }
                I[i] = x;
        }
        build(0);
        for (int u = n; u >= 1; u--) {
                if (!I[u]) continue;
                int p = get(I[u]);
                upd(0, n-u+1, n-u+1, I[u]);
                p = n-p+1;
                par[u] = p;
        }
        build(1);
        for (int u = n; u >= 1; u--) {
                if (!I[u]) continue;
                upd(1, I[u], u, 1);
        }
        for (int u = 1; u <= n; u++) vis[u] = 0;
        vis[n+1] = 1;
        for (int t = 1; t <= d; t++) {
                int u = out[1];
                ans += seg[1];
                while (!vis[u]) {
                        upd(1, I[u], u, -1);
                        vis[u] = 1;
                        u = par[u];
                }
        }
        cout << n-ans << endl;

}
int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        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