Submission #407563

#	Time	Username	Problem	Language	Result	Execution time	Memory
407563		maomao90	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	552 ms	219248 KiB

prison

#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1: 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ii> vii;

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 2000005

int n, d, t;
int ti[MAXN];
stack<ii> stk;
bool alr[MAXN], die[MAXN];
vi adj[MAXN];
int prv[MAXN], p[MAXN];
int ans;
priority_queue<ii> pq;

int dp[MAXN];
void dfs(int u) {
	p[u] = -1;
	for (int v : adj[u]) {
		dfs(v);
		if (mxto(dp[u], dp[v] + 1)) {
			p[u] = v;
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &d, &t);
	REP (i, 1, n + 1) {
		scanf("%d", &ti[i]);
	}
	REP (i, 1, n + 1) {
		while (!stk.empty() && stk.top().FI < i) stk.pop();
		if (ti[i] <= t) {
			int nxt = i + t - ti[i];
			stk.push(MP(nxt, i));
			alr[i] = 1;
		} else {
			if (stk.empty()) {
				die[i] = 1;
				ans++;
			} else {
				prv[i] = stk.top().SE;
			}
		}
	}
	while (!stk.empty()) stk.pop();
	REP (i, 1, n + 1) {
		if (die[i] || alr[i]) continue;
		while (!stk.empty() && stk.top().FI > prv[i]) {
			adj[i].pb(stk.top().FI);
			stk.pop();
		}
		stk.push(MP(i, -1));
	}
	//REP (i, 1, n + 1) {
		//printf("%d:", i);
		//for (int v : adj[i]) {
			//printf(" %d", v);
		//}
		//printf("\n");
	//}
	while (!stk.empty()) {
		int tp = stk.top().FI; stk.pop();
		dfs(tp);
		pq.push(MP(dp[tp], tp));
	}
	while (!pq.empty() && d) {
		auto [l, u] = pq.top(); pq.pop();
		ans += l + 1;
		while (p[u] != -1) {
			for (int v : adj[u]) {
				if (v == p[u]) continue;
				pq.push(MP(dp[v], v));
			}
			u = p[u];
		}
		d--;
	}
	ans = n - ans;
	printf("%d\n", ans);
	return 0;
}

/*
5 1 42                          
13 37 47 11 42

5 2 5 
1 9 4 6 7
*/

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d%d", &n, &d, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
prison.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d", &ti[i]);
      |   ~~~~~^~~~~~~~~~~~~~

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