oj.uz

Submission #970233

# Submission time Handle Problem Language Result Execution time Memory
970233 2024-04-26T08:46:48 Z amirhoseinfar1385 The short shank; Redemption (BOI21_prison) C++17
20 / 100
 653 ms 209300 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
const int maxn=2000000+10;
int n,k,t,inf=1e9+5;
int all[maxn],te=0,res=0,vas[maxn],kaf=(1<<21);
pair<int,int>allq[maxn];

void fastscan(int &number) 
{ 
    register int c; 
    number = 0; 
    c = getchar(); 
    for (; (c>47 && c<58); c=getchar()) 
        number = number *10 + c - 48; 
} 

struct segment{
	struct node{
		int lazy;
		pair<int,int>mx;
		node(){
			lazy=0;
			mx=make_pair(0,0);
		}
	};
	node seg[(1<<22)];
	segment(){
		for(int i=(1<<22)-1;i>=1;i--){
			if(i>=kaf){
				seg[i].mx.second=i-kaf;
			}else{
				seg[i].mx.second=seg[(i<<1)].mx.second;
			}
		}
	}
	void calc(int i){
		if(i>=kaf){
			seg[i].mx.first+=seg[i].lazy;
			seg[i].lazy=0;
			return ;
		}
		seg[i].mx=max(make_pair(seg[(i<<1)].lazy+seg[(i<<1)].mx.first,seg[(i<<1)].mx.second),make_pair(seg[(i<<1)^1].lazy+seg[(i<<1)^1].mx.first,seg[(i<<1)^1].mx.second));
	}
	void shift(int i){
		if(i>=kaf){
			return ;
		}
		if(seg[(i<<1)].lazy==0){
			return ;
		}
		seg[(i<<1)].lazy+=seg[i].lazy;
		seg[(i<<1)^1].lazy+=seg[i].lazy;
		seg[i].lazy=0;
		return ;
	}
	void upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].lazy+=w;
			shift(i);
			calc(i);
			return ;
		}
		shift(i);
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}
	pair<int,int> pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return make_pair(0,-1);
		}
		shift(i);
		calc(i);
		if(l>=tl&&r<=tr){
			return seg[i].mx;
		}
		int m=(l+r)>>1;
		return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
	}
}segmx;

void remove(int ind){
	if(vas[ind]==1){
		return ;
	}
	vas[ind]=1;
	segmx.upd(1,0,kaf-1,allq[ind].first,allq[ind].second,-1);
}

struct segmentv{
	vector<int>seg[(1<<22)];
	char hey[(1<<22)];
	void upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].push_back(w);
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		return ;
	}
	void del(int i){
		i+=kaf;
		while(i>0){
			if(hey[i]==0){
				for(auto x:seg[i]){
					remove(x);
				}
				hey[i]=1;
			}
			i>>=1;
		}
	}
}segv;

void vorod(){
	//cin>>n>>k>>t;
	fastscan(n);
	fastscan(k);
	fastscan(t);
	for(int i=1;i<=n;i++){
		//cin>>all[i];
		fastscan(all[i]);
	}
}

void calbaz(){
	all[0]=inf;
	vector<int>v;
	v.push_back(0);
	for(int i=1;i<=n;i++){
		while((int)v.size()>0&&all[v.back()]+(i-v.back())>=all[i]){
			v.pop_back();
		}
		while((int)v.size()>0&&all[v.back()]+(i-v.back())>t){
			v.pop_back();
		}
		if(all[i]>t){
			if((int)v.size()==0){
				res++;
			}else{
				allq[te]=(make_pair(v.back(),i-1));
				te++;
			}
		}
		v.push_back(i);
	}
}

void aval(){
	for(int i=0;i<te;i++){
		segmx.upd(1,0,kaf-1,allq[i].first,allq[i].second,1);
		segv.upd(1,0,kaf-1,allq[i].first,allq[i].second,i);
	}
}

void pre(){
	calbaz();
	aval();
}

void khor(){
	res=n-res;
	cout<<res<<"\n";
}

void cal(){
//	int ind=getmx();
	pair<int,int>gm=segmx.pors(1,0,kaf-1,0,n+1);
	if(gm.first==0){
		khor();
		exit(0);		
		return ;
	}
	res+=gm.first;
	segv.del(gm.second);
}

void solve(){
	for(int i=0;i<k;i++){
		cal();
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
	khor();
}

Compilation message

prison.cpp: In function 'void fastscan(int&)':
prison.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 150356 KB Output is correct
2 Correct 37 ms 150100 KB Output is correct
3 Correct 36 ms 150096 KB Output is correct
4 Correct 37 ms 150100 KB Output is correct
5 Correct 38 ms 150096 KB Output is correct
6 Incorrect 40 ms 150108 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 150096 KB Output is correct
2 Correct 162 ms 161872 KB Output is correct
3 Correct 130 ms 158720 KB Output is correct
4 Correct 192 ms 164336 KB Output is correct
5 Correct 247 ms 169028 KB Output is correct
6 Correct 181 ms 163688 KB Output is correct
7 Correct 653 ms 209300 KB Output is correct
8 Correct 207 ms 166708 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 150356 KB Output is correct
2 Correct 37 ms 150100 KB Output is correct
3 Correct 36 ms 150096 KB Output is correct
4 Correct 37 ms 150100 KB Output is correct
5 Correct 38 ms 150096 KB Output is correct
6 Incorrect 40 ms 150108 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 150108 KB Output is correct
2 Correct 64 ms 152404 KB Output is correct
3 Correct 56 ms 152012 KB Output is correct
4 Correct 88 ms 154724 KB Output is correct
5 Correct 94 ms 155632 KB Output is correct
6 Correct 99 ms 156108 KB Output is correct
7 Correct 58 ms 152132 KB Output is correct
8 Correct 57 ms 152164 KB Output is correct
9 Correct 116 ms 157956 KB Output is correct
10 Correct 50 ms 151768 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 150356 KB Output is correct
2 Correct 37 ms 150100 KB Output is correct
3 Correct 36 ms 150096 KB Output is correct
4 Correct 37 ms 150100 KB Output is correct
5 Correct 38 ms 150096 KB Output is correct
6 Incorrect 40 ms 150108 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 150356 KB Output is correct
2 Correct 37 ms 150100 KB Output is correct
3 Correct 36 ms 150096 KB Output is correct
4 Correct 37 ms 150100 KB Output is correct
5 Correct 38 ms 150096 KB Output is correct
6 Incorrect 40 ms 150108 KB Output isn't correct
7 Halted 0 ms 0 KB -