Submission #863222

#	Time	Username	Problem	Language	Result	Execution time	Memory
863222		arashMLG	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	353 ms	303784 KiB

prison

#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;

const int N = 2e6 + 23;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)
// https://oj.uz/problem/view/BOI21_prison

int n,d,T;
int a[N];
stack<int> st;
vector<int> G[N];
int h[N],par[N];
pii mh[N];
vector<int> hs[N];
int l[N];
int ans;

void calcl() {
	for(int i = 1; i<= n ; i++) {
		if(a[i] <= T) {
			l[i] =i;
			st.push(i);
			continue;;
		}
		debug(sz(st));
		while(sz(st) && (i - st.top()) + a[st.top()] > T) debug(st.top()),st.pop();
		if(sz(st)) l[i] = st.top();
		st.push(i);
	}
}

bool isroot[N];

void buildg() {
	ans = n;
	while(sz(st)) st.pop();
	for(int i = n; i>=1 ; i--) {
		debug(i,l[i]);
		if(a[i] <= T) continue;
		if(l[i] == 0) {
			ans--;
			continue;
		}
		while(sz(st) && l[st.top()] > i) st.pop();
		if(sz(st)) G[st.top()].pb(i);
		else isroot[i] = true;
		st.push(i);
	}
}

void dfs(int v) {
	mh[v] = {h[v],v};
	debug(v,G[v]);
	for(int u : G[v]) {
		h[u] = h[v] +1;
		par[u] = v;
		dfs(u);
		mh[v] = max(mh[v] ,mh[u]);
	}
}

bool mark[N];

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>d>>T;
	for(int i = 1; i<= n ; i ++) cin>>a[i];
	calcl();
	buildg();
	for(int i = 1; i<= n ; i ++) {
		if(isroot[i]) {
			par[i] = i;
			debug(i);
			dfs(i);
			hs[mh[i].F+1].pb(i);
		}
	}
	for(int i = N-1; i >= 0; i --) {
		for(int sex : hs[i]) {
			if(d == 0) {
				cout<<ans << '\n';
				return 0;
			}
			ans -= i;
			d--;
			int x = mh[sex].S;
			while(!mark[x]) {
				mark[x] = true;
				for(int u : G[x]) if(!mark[u]) {
					hs[mh[u].F-h[u]+1].pb(u);
				}
				x= par[x];
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}

Compilation message (stderr)

prison.cpp: In function 'void calcl()':
prison.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
prison.cpp:42:3: note: in expansion of macro 'debug'
   42 |   debug(sz(st));
      |   ^~~~~
prison.cpp:5:20: warning: left operand of comma operator has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
prison.cpp:43:53: note: in expansion of macro 'debug'
   43 |   while(sz(st) && (i - st.top()) + a[st.top()] > T) debug(st.top()),st.pop();
      |                                                     ^~~~~
prison.cpp: In function 'void buildg()':
prison.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
prison.cpp:55:3: note: in expansion of macro 'debug'
   55 |   debug(i,l[i]);
      |   ^~~~~
prison.cpp: In function 'void dfs(int)':
prison.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
prison.cpp:70:2: note: in expansion of macro 'debug'
   70 |  debug(v,G[v]);
      |  ^~~~~
prison.cpp: In function 'int32_t main()':
prison.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
prison.cpp:90:4: note: in expansion of macro 'debug'
   90 |    debug(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