Submission #672864

#	Time	Username	Problem	Language	Result	Execution time	Memory
672864		Kahou	The short shank; Redemption (BOI21_prison)	C++14	80 / 100	2105 ms	138488 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, st[N], ft[N], tim, id[N], par[N];
int seg[N<<2], lazy[N<<2];
bool vis[N];
vector<int> adj[N];
int I[N];
pii seg2[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 (tl == tr) {
		seg[u] = min(seg[u], x);
		return;
	}
	int md = (tl+tr)/2;
	int lc = u<<1;
	int rc = u<<1|1;
	if (id <= md) upd(id, x, lc, tl, md);
	else 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 build2(int u=1, int tl=1, int tr=n) {
	if (tl == tr) {
		seg2[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);
	seg2[u] = max(seg2[lc], seg2[rc]);
}
void shift(int u) {
	int lc = u<<1;
	int rc = u<<1|1;
	seg2[lc].F += lazy[u];
	lazy[lc] += lazy[u];
	seg2[rc].F += lazy[u];
	lazy[rc] += lazy[u];
	lazy[u] = 0;
}
void upd2(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) {
		seg2[u].F += x;
		lazy[u] += x;
		return;
	}
	shift(u);
	int md = (tl+tr)/2;
	int lc = u<<1;
	int rc = u<<1|1;
	upd2(l, r, x, lc, tl, md), upd2(l, r, x, rc, md+1, tr);
	seg2[u] = max(seg2[lc], seg2[rc]);
}

void solve() {
	cin >> n >> d >> T;
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
	}
	build();
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		upd(i, t[i]-i);
		int x = get(T-i)+1;
		if (x > i) continue;
		if (x <= 1) {
			ans++;
			continue;
		}
		I[i] = x;
	}
	build();
	for (int u = n; u >= 1; u--) {
		if (!I[u]) continue;
		int p = get(I[u]);
		upd(n-u+1, I[u]);
		if (!p) continue;
		p = n-p+1;
		par[u] = p;
	}
	build2();
	for (int u = n; u >= 1; u--) {
		if (!I[u]) continue;
		upd2(I[u], u, 1);
	}
	for (int u = 1; u <= n; u++) vis[u] = 0;
	vis[0] = 1;
	for (int t = 1; t <= d; t++) {
		int u = seg2[1].S;
		ans += seg2[1].F;
		while (!vis[u]) {
			upd2(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