Submission #868562

#	Time	Username	Problem	Language	Result	Execution time	Memory
868562		NaimSS	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	353 ms	256956 KiB

prison

#include <bits/stdc++.h>
#define sz(v) ((int)v.size())
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define sz(v) ((int)v.size())
#define all(v) begin(v),end(v)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;

void dbg_out() { cerr << endl ;}
template<typename Head, typename... Tail> void dbg_out(Head H,Tail... T){
	cerr<<' '<<H ;
	dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr<<"("<< #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__), cerr << endl;
#else 
#define dbg(...) 42
#endif

const int N = 2e6 + 10;
int t[N];
int nxt[N];
int H[N];
int id[N];
int vis[N];
vi g[N];

void dfs(int v,int p=-1){
	if(p==-1)H[v] = 0;
	vis[v] = 1;
	for(auto to : g[v])if(to!=p){
		H[to] = H[v] + 1;
		assert(!vis[to]);
		dfs(to,v);
	}
}

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,d,T;
	cin >> n >> d >> T;
	rep(i,1,n+1)cin >> t[i];

	int ans = n;
	int Mx=0;

	stack<pii> S;
	int curId=0;
	for(int i=1;i<=n;i++){
		int cur = i + T - t[i];
		Mx = max(Mx,cur);
		if(!S.empty())S.top().ss = max(S.top().ss, cur);
		if(t[i] > T){
			if(Mx < i){
				ans--;
				continue;
			}
			int last = -1;
			while(!S.empty()){
				int cur = S.top().ff;
				last = max(last, S.top().ss);
				if(last >= i)break;
				dbg(cur , id[cur], last);
				nxt[id[cur]] = curId;
				S.pop();
			}
			S.push({i, -1});
			id[i] = curId++;
			nxt[id[i]] = -1;
			dbg(i,id[i]);
		}
	}
	for(int i=0;i<curId;i++){
		assert(nxt[i] == -1 || nxt[i] > i);
		if(nxt[i]!=-1){
			g[nxt[i]].pb(i);
		}
	}
	per(i,0,curId)if(!vis[i]){
		dfs(i);
	}
	vi ids;
	rep(i,0,curId)ids.pb(i);
	sort(all(ids),[&](int a,int b){
		return H[a] > H[b];
	});
	memset(vis,0,sizeof(vis));
	priority_queue<int> pq;
	for(auto i : ids){
		int val = 0;
		while(i!=-1 && !vis[i]){
			vis[i] = 1,val++;
			i = nxt[i];
		}
		pq.push(val);
	}
	while(d-- && sz(pq))ans -= pq.top(),pq.pop();
	cout << ans << endl;
}

Compilation message (stderr)

prison.cpp: In function 'int32_t main()':
prison.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define dbg(...) 42
      |                  ^~
prison.cpp:71:5: note: in expansion of macro 'dbg'
   71 |     dbg(cur , id[cur], last);
      |     ^~~
prison.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define dbg(...) 42
      |                  ^~
prison.cpp:78:4: note: in expansion of macro 'dbg'
   78 |    dbg(i,id[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