Submission #528387

#	Time	Username	Problem	Language	Result	Execution time	Memory
528387		fatemetmhr	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1113 ms	246940 KiB

prison

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn5 = 2e6 + 10;
const int maxnt = 8e6 + 10;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x)  x.begin(), x.end()

int n, ti = -1, st[maxn5], ft[maxn5], lazy[maxnt];
int h[maxn5], l[maxn5], ver[maxn5], ans = 0;
int per[maxn5], par[maxn5];
pair <int, int> mx[maxnt];
vector <int> adj[maxn5];
vector <pair<ll, int>> av;
set <pair<int, int>> seg;
bool mark[maxn5];

inline bool cmp(int i, int j){
	return i - l[i] < j - l[j];
}

inline void add(int l, int r, int lq, int rq, int v){
	if(rq <= l || r <= lq)
		return;
	if(lq <= l && r <= rq){
		lazy[v]--;
		mx[v].fi--;
		return;
	}
	int mid = (l + r) >> 1;
	add(l, mid, lq, rq, v * 2);
	add(mid, r, lq, rq, v * 2 + 1);
	mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	mx[v].fi += lazy[v];
	return;
}

inline void build(int l, int r, int v){
	if(r - l == 1){
		mx[v] = l > ti ? mp(-1, 0) : mp(h[ver[l]] + 1, ver[l]);
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, v * 2);
	build(mid, r, v * 2 + 1);
	mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	return;
}

inline void upd(int v){
	ans++;
	mark[v] = true;
	add(0, n, st[v], ft[v] + 1, 1);
	if(par[v] != -1 && !mark[par[v]])
		upd(par[v]);
	return;
}

inline void dfs(int v){
	st[v] = ++ti;
	ver[ti] = v;
	for(auto u : adj[v]){
		h[u] = h[v] + 1;
		dfs(u);
	}
	ft[v] = ti;
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int d; ll tim; cin >> n >> d >> tim;
	for(int i = 0; i < n; i++){
		ll t; cin >> t;
		while(av.size() && av.back().fi >= t - i)
			av.pop_back();
		av.pb({t - i, i});
		
		int p = upper_bound(all(av), mp(tim - i, maxn5)) - av.begin();
		p--;
		ans += (p == -1);
		if(p == -1 || av[p].se == i)
			l[i] = -maxn5;
		else
			l[i] = av[p].se;
		per[i] = i;
	}
	
	sort(per, per + n, cmp);
	memset(par, -1, sizeof par);
	
	for(int i = 0; i < n; i++) if(l[i] >= 0){
		auto it = seg.lower_bound(mp(l[i], -1));
		for(; it != seg.end() && (it ->se) <= i;){
			adj[i].pb(it->se);
			par[it->se] = i;
			auto itt = it;
			it++;
			seg.erase(itt);
		}
		seg.insert(mp(l[i], i));
	}
	
	for(int i = 0; i < n; i++) if(l[i] >= 0 && par[i] == -1)
		dfs(i);
	
	build(0, n, 1);
	
	for(int i = 0; i < d && mx[1].fi > 0; i++){
		int v = mx[1].se;
		upd(v);
	}
	cout << n - ans << endl;
}

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