Submission #863225

#	Time	Username	Problem	Language	Result	Execution time	Memory
863225		arashMLG	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1172 ms	430224 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 int inf = 1e9+7;

#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)
//#define int     ll

#pragma GCC optimize("O3,unroll-loops")

int n,d,T;
int a[N];
int l[N];
stack<int> st;

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


struct Seg {
	pii t[N<<2];
	int lz[N<<2];
	
	void build(int v=1,int tl = 0 ,int tr = N){ 
		if(tr- tl == 1) {
			t[v] = {0,tl};
			return;
		}
		int mid=(tl+tr)/2;
		build(lc,tl,mid);
		build(rc,mid,tr);
		t[v] = max(t[lc],t[rc]);
	}
	
	void shift(int v) {
		if(lz[v] == 0) return;
		t[lc].F += lz[v];
		t[rc].F += lz[v];
		lz[lc] += lz[v];
		lz[rc] += lz[v];
		lz[v] = 0;
	}
	
	void upd(int l,int r,int x,int v=1,int tl =0 ,int tr =N) {
		if(l > r) return;
		if(l == tl && r == tr-1) {
			t[v].F += x;
			lz[v] += x;
			return;
		}
		shift(v);
		int mid=(tl+tr)/2;
		upd(l,min(mid-1,r),x,lc,tl,mid);
		upd(max(l,mid),r,x,rc,mid,tr);
		t[v] = max(t[lc],t[rc]);
	}
	
	/*pii gmx(int l,int r,int v=1,int tl=0,int tr = N) {
		if(l > r) return 0;
		if(l == tl && r == tr-1) return t[v];
		shift(v);
		int mid=(tl +tr)/2;
		return max( gmx
	}*/
	
} s;

vector<int> G[N],GP[N];

int ans;

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

bool mark[N];
int St[N],ft[N];
int h[N];
int timer;
int par[N];

void dfs1(int v) {
	St[v] = timer ++;
	for(int u : G[v]) {
		dfs1(u);
		GP[St[v]].pb(St[u]);
	}
}

void dfs2(int v) {
	ft[v] = v;
	for(int u : GP[v]) {
		h[u] = h[v] +1;
		par[u] = v;
		dfs2(u);
		ft[v] = ft[u];
	}
	s.upd(v,ft[v],1);
}

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();
	
	ans =n;
	buildg();
	
	s.build();
	dfs1(0);
	h[0] =1;
	dfs2(0);
	while(s.t[1].F != 0 && d>0) {
		int x = s.t[1].S;
		if(sz(GP[x]) != 0) break;
		d--;
		while(!mark[x]) {
			mark[x] = true;
			if(x !=0)
				ans--;
			s.upd(x,ft[x],-1);
			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:37:4: note: in expansion of macro 'debug'
   37 |    debug(i,l[i]);
      |    ^~~~~
prison.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
prison.cpp:44:3: note: in expansion of macro 'debug'
   44 |   debug(i,l[i]);
      |   ^~~~~
prison.cpp: In function 'void buildg()':
prison.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
prison.cpp:114:3: note: in expansion of macro 'debug'
  114 |   debug(st.top(),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