oj.uz

Submission #407013

# Submission time Handle Problem Language Result Execution time Memory
407013 2021-05-18T10:47:51 Z jamezzz The short shank; Redemption (BOI21_prison) C++14
10 / 100
 168 ms 133648 KB 
#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])--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);
		}
	}
	for(int i=0;i<n;++i){
		if(rng[i].fi!=-1&&par[i]==-1){
			dfs(i);
			pq.push(dep[i]);
			//pf("%d: %d %d\n",i,dep[i].fi,dep[i].se);
		}
	}
	for(int i=0;i<d;++i){
		if(pq.empty())break;
		int src=pq.top().se;pq.pop();
		block(src);
	}
	pf("%d\n",ans+tot);
}

Compilation message

prison.cpp: In function 'int main()':
prison.cpp:68:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  sf("%d%d%d",&n,&d,&t);
      |    ^
prison.cpp:72:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   sf("%d",&a[i]);
      |     ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55108 KB Output is correct
2 Correct 31 ms 55080 KB Output is correct
3 Correct 29 ms 55040 KB Output is correct
4 Correct 29 ms 55144 KB Output is correct
5 Correct 29 ms 55128 KB Output is correct
6 Correct 28 ms 55108 KB Output is correct
7 Correct 29 ms 55116 KB Output is correct
8 Correct 28 ms 55092 KB Output is correct
9 Incorrect 29 ms 55084 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 55088 KB Output is correct
2 Correct 131 ms 76588 KB Output is correct
3 Correct 126 ms 75124 KB Output is correct
4 Correct 125 ms 79740 KB Output is correct
5 Correct 146 ms 76960 KB Output is correct
6 Correct 121 ms 79036 KB Output is correct
7 Correct 168 ms 133648 KB Output is correct
8 Correct 126 ms 81040 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55108 KB Output is correct
2 Correct 31 ms 55080 KB Output is correct
3 Correct 29 ms 55040 KB Output is correct
4 Correct 29 ms 55144 KB Output is correct
5 Correct 29 ms 55128 KB Output is correct
6 Correct 28 ms 55108 KB Output is correct
7 Correct 29 ms 55116 KB Output is correct
8 Correct 28 ms 55092 KB Output is correct
9 Incorrect 29 ms 55084 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55028 KB Output is correct
2 Correct 48 ms 59164 KB Output is correct
3 Correct 45 ms 58812 KB Output is correct
4 Incorrect 48 ms 62216 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55108 KB Output is correct
2 Correct 31 ms 55080 KB Output is correct
3 Correct 29 ms 55040 KB Output is correct
4 Correct 29 ms 55144 KB Output is correct
5 Correct 29 ms 55128 KB Output is correct
6 Correct 28 ms 55108 KB Output is correct
7 Correct 29 ms 55116 KB Output is correct
8 Correct 28 ms 55092 KB Output is correct
9 Incorrect 29 ms 55084 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55108 KB Output is correct
2 Correct 31 ms 55080 KB Output is correct
3 Correct 29 ms 55040 KB Output is correct
4 Correct 29 ms 55144 KB Output is correct
5 Correct 29 ms 55128 KB Output is correct
6 Correct 28 ms 55108 KB Output is correct
7 Correct 29 ms 55116 KB Output is correct
8 Correct 28 ms 55092 KB Output is correct
9 Incorrect 29 ms 55084 KB Output isn't correct
10 Halted 0 ms 0 KB -