Submission #407100

#	Time	Username	Problem	Language	Result	Execution time	Memory
407100		jamezzz	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	538 ms	272344 KiB

prison

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define mxto(x,y) x=max(x,(__typeof__(x))y)
typedef pair<int, int> ii;
typedef vector<int> vi;

int n,d,t,a[2000005],par[2000005],tot;
ii rng[2000005],dep[2000005];
vi AL[2000005],root;
bool blocked[2000005];
stack<ii> s;
stack<int> s2;
priority_queue<ii> pq;

void dfs(int u){
	dep[u]=ii(1,u);
	for(int v:AL[u]){
		dfs(v);
		mxto(dep[u],ii(dep[v].fi+1,dep[v].se));
	}
}

void block(int u){
	if(blocked[u])return;
	--tot; //this guy will not riot
	blocked[u]=true;
	for(int v:AL[u]){
		if(!blocked[v])pq.push(dep[v]);
		//push in other subtrees
	}
	if(par[u]==-1)return;
	block(par[u]);
	//"parent" gets blocked
}

int main(){
	sf("%d%d%d",&n,&d,&t);
	int ans=0;
	for(int i=0;i<n;++i){
		sf("%d",&a[i]);
		while(!s.empty()&&s.top().fi+i-s.top().se>t)s.pop(); //this element is now useless
		if(a[i]>t){
			if(!s.empty()){
				rng[i]=ii(s.top().se,i-1);
				//placing a mattress in this range will make this guy not riot
				//otherwise he will riot
				++tot;
				//increment the count of "uncertain" people
			}
			else rng[i]=ii(-1,-1); //this guy will always not riot
		}
		else{
			++ans;
			rng[i]=ii(-1,-1);
			//this guy will always riot
			s.push(ii(a[i],i));
			//might make some other guys riot
		}
	}
	memset(par,-1,sizeof par);
	for(int i=0;i<n;++i){
		if(rng[i].fi!=-1){
			while(!s2.empty()&&rng[i].fi<=s2.top()&&s2.top()<=rng[i].se){
				par[s2.top()]=i;
				//i is the first person who will not riot when putting a
				//mattress before s2.top() (other than himself)
				AL[i].pb(s2.top());
				s2.pop();
			}
			s2.push(i);
		}
	}
	for(int i=0;i<n;++i){
		if(rng[i].fi!=-1&&par[i]==-1){
			dfs(i);
			//dfs to find the depth and the leaf with the largest depth in the subtree
			pq.push(dep[i]);
		}
	}
	for(int i=0;i<d;++i){
		//greedily take the guy with the highest depth
		if(pq.empty())break;
		int src=pq.top().se;pq.pop();
		block(src);
	}
	pf("%d\n",ans+tot);
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:43:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  sf("%d%d%d",&n,&d,&t);
      |    ^
prison.cpp:46:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   sf("%d",&a[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