Submission #672809

#	Time	Username	Problem	Language	Result	Execution time	Memory
672809		radal	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2107 ms	358488 KiB

prison

/* 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, b[N], L[N], vis[N];
int seg[N<<2];
pii out[N<<2];
int lazy[N<<2];
vector<int> vc[N<<2];
 
void build(int u=1, int tl=1, int tr=n) {
    if (tl == tr) {
        seg[u] = inf;
        return;
    }
    int md = (tl+tr)/2;
    int lc = u<<1;
    int rc = u<<1|1;
    build(lc, tl, md), build(rc, md+1, tr);
    seg[u] = min(seg[lc], seg[rc]);
}
 
void upd(int id, int x, int u=1, int tl=1, int tr=n) {
    if (id < tl || tr < id) return;
    if (tl == tr) {
        seg[u] = min(seg[u], x);
        return;
    }
    int md = (tl+tr)/2;
    int lc = u<<1;
    int rc = u<<1|1;
    upd(id, x, lc, tl, md), upd(id, x, rc, md+1, tr);
    seg[u] = min(seg[lc], seg[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 shift(int u) {
    int lc = u<<1;
    int rc = u<<1|1;
    out[lc].F += lazy[u];
    lazy[lc] += lazy[u];
    out[rc].F += lazy[u];
    lazy[rc] += lazy[u];
    lazy[u] = 0;
}
void build2(int u=1, int tl=1, int tr=n) {
    if (tl == tr) {
        out[u] = {0, tl};
        return;
    }
    int md = (tl+tr)/2;
    int lc = u<<1;
    int rc = u<<1|1;
    build2(lc, tl, md), build2(rc, md+1, tr);
    out[u] = max(out[lc], out[rc]);
}
void push(int l, int r, int id, int u =1, int tl=1, int tr=n) {
    if (r < tl || tr < l) return;
    if (l <= tl && tr <= r) {
        out[u].F++;
        lazy[u]++;
        vc[u].push_back(id);
        return;
    }
    shift(u);
    int md = (tl+tr)/2;
    int lc = u<<1;
    int rc = u<<1|1;
    push(l, r, id, lc, tl, md), push(l, r, id, rc, md+1, tr);
    out[u] = max(out[lc], out[rc]);
}
void pop(int l, int r, int id, int u=1, int tl=1, int tr=n) {
    if (r < tl || tr < l) return;
    if (l <= tl && tr <= r) {
        out[u].F--;
        lazy[u]--;
        vc[u].pop_back();
        return;
    }
    shift(u);
    int md = (tl+tr)/2;
    int lc = u<<1;
    int rc = u<<1|1;
    pop(l, r, id, lc, tl, md), pop(l, r, id, rc, md+1, tr);
    out[u] = max(out[lc], out[rc]);
}
bool cmp (int x, int y) {
    pii A = {x-L[x], x};
    pii B = {y-L[y], y};
    return A < B;
}
 
vector<int> vx;
void getvc(int id, int u=1, int tl=1, int tr=n) {
    for (int i = (int)vc[u].size()-1; i >= 0; i--) {
        int x = vc[u][i];
        vx.push_back(x);
    }
    if (tl == tr) return;
    shift(u);
    int md = (tl+tr)/2;
    int lc = u<<1;
    int rc = u<<1|1;
    if (id <= md) getvc(id, lc, tl, md);
    else getvc(id, rc, md+1, tr);
}
 
void solve() {
    cin >> n >> d >> T;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    build();
    build2();
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        upd(i, t[i]-i);
        L[i] = get(T-i)+1;
        if (L[i] > i) continue;
        if (L[i] <= 1) {
            ans++;
            continue;
        }
        push(L[i], i, i);
    }
    for (int u = 1; u <= (n<<2); u++) {
        if (!vc[u].empty()) sort(vc[u].begin(), vc[u].end(), cmp);
    }
    for (int i = 1; i <= d; i++) {
        ans += out[1].F;
        int id = out[1].S;
        getvc(id);
        for (int j = (int)vx.size()-1; j >= 0; j--) {
            int x = vx[j];
            pop(L[x], x, x);
        }
        vx.clear();
    }
    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