제출 #444324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444324		8e7	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	547 ms	235680 KiB

prison

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) {cout << a << " ", debug(b ...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 2000005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);
int rig[maxn], dep[maxn], ma[maxn];
vector<int> adj[maxn], val;
stack<int> stk, tree;
void dfs(int n, int par, int d) {
	dep[n] = d;
	for (int v:adj[n]) dfs(v, n, d + 1), dep[n] = max(dep[n], dep[v]);
}
void dfs2(int n, int par, int to, int d) {
	ma[to] = max(ma[to], dep[to] - d + 1);
	int best = 0, bind = 0;
	for (int v:adj[n]) {
		if (dep[v] > best) best = dep[v], bind = v;
	}
	for (int v:adj[n]) {
		if (v == bind) dfs2(v, n, to, d + 1);
		else dfs2(v, n, v, d + 1);
	}
}
int main() {
	io
	int n, k, t;
	cin >> n >> k >> t;
	for (int i = 1;i <= n;i++) {
		int ti;
		cin >> ti;
		if (ti <= t) {
			rig[i] = min(n, i + t - ti); //[i, a[i]]
		} 
	}
	int cnt = 0;
	for (int i = n;i > 0;i--) {
		if (rig[i]) {
			cnt++;
			while (stk.size() && rig[i] >= stk.top()) {
				int cur = stk.top();stk.pop();	
				cnt++;
				while (tree.size() && cur > tree.top()) {
					adj[cur].push_back(tree.top());
					tree.pop();
				}
				tree.push(cur);
			}
		} else {
			stk.push(i);
		}
	}	
	while (tree.size()) {
		adj[0].push_back(tree.top()), tree.pop();
	}
	dfs(0, 0, 0);
	dfs2(0, 0, 0, 0);
	for (int i = 0;i <= n;i++) {
		if (ma[i]) val.push_back(ma[i]);
	}
	sort(val.begin(), val.end(), [&] (int x, int y) {return x > y;});
	for (int i = 0;i < min(k, int(val.size()));i++) cnt -= val[i];
	cout << cnt + 1 << endl;
}
/*
5 1 42
13 37 47 11 42
5 2 5
1 9 4 6 7

6 2 6
1 3 5 8 9 10
  */

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