Submission #407096

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

prison

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;
 
typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements
 
#define DEBUG
 
#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

int n,d,t,a[2000005],last[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;
	blocked[u]=true;
	for(int v:AL[u]){
		if(!blocked[v])pq.push(dep[v]);
	}
	if(par[u]==-1)return;
	block(par[u]);
}

int main(){
	sf("%d%d%d",&n,&d,&t);
	int ans=0;
	last[0]=-1;
	for(int i=0;i<n;++i){
		sf("%d",&a[i]);
		while(!s.empty()&&s.top().fi+i-s.top().se>t)s.pop();
		if(a[i]>t){
			if(!s.empty()){
				rng[i]=ii(s.top().se,i-1);
				++tot;
			}
			else rng[i]=ii(-1,-1);
		}
		else{
			++ans;
			rng[i]=ii(-1,-1);
			s.push(ii(a[i],i));
		}
		if(i!=0)last[i]=last[i-1];
		if(rng[i].fi!=-1)last[i]=i;
		//if rng[i]!=(-1,-1) this guy has a[i]>t but will riot
		//placing a mattress in rng[i] will make this guy not riot
		//not placing a mattress inside will make this guy 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;
				AL[i].pb(s2.top());
				s2.pop();
			}
			s2.push(i);
			//find the next element such that putting mattress to the 
			//left of this guy will make him not riot
		}
	}
	for(int i=0;i<n;++i){
		if(rng[i].fi!=-1&&par[i]==-1){
			dfs(i);
			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:69:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  sf("%d%d%d",&n,&d,&t);
      |    ^
prison.cpp:73:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   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