Submission #429732

#	Time	Username	Problem	Language	Result	Execution time	Memory
429732		keta_tsimakuridze	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	2080 ms	6748 KiB

prison

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int> 
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,tree[4*N],n,a[N],lazy[4*N],ans,D;
pair<int,int> tr[4*N];
pair<int,int> w[4*N];
void build(int u,int l,int r){
	if(l==r)  {
		tree[u] = a[l] - l; tr[u].s = l;
		return;
	}
	int mid=(l+r)/2;
	build(2*u,l,mid);
	build(2*u+1,mid+1,r);
	tree[u] = min(tree[2*u],tree[2*u+1]);
}
int getans(int u,int start,int end,int l,int r) {
	if(l>end || r<start) return t+55;
	if(start<=l && r<=end) return tree[u];
	int mid=(l+r)/2;
	return min(getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r));
}
void update(int u,int start,int end,int l,int r,int val) {
	if(lazy[u]) {
		tr[u].f += lazy[u];
		if(l!=r){
			lazy[2*u] += lazy[u];
			lazy[2*u+1] += lazy[u];
		}
		lazy[u] = 0;
	}
	if(l>end || r<start) return;
	if(start<=l && r<=end) {
		lazy[u] = val;
		tr[u].f += lazy[u];
		if(l!=r){
			lazy[2*u] += lazy[u];
			lazy[2*u+1] += lazy[u];
		}
		lazy[u] = 0;		
		return;
	} 
	int mid = (l+r)/2;
	update(2*u,start,end,l,mid,val);
	update(2*u+1,start,end,mid+1,r,val);
	tr[u] = tr[2*u+1];
	tr[u] = max(tr[2*u],tr[2*u+1]);
}
void insert(int u,int ind,int l,int r,int st,int en) {
	if(l>ind || r<ind) return; 
	if(l==r) {
		w[u] = {st,en};
		return;
	}
	int mid = (l+r)/2;
	insert(2*u,ind,l,mid,st,en);
	insert(2*u+1,ind,mid+1,r,st,en);
	w[u] = min(w[2*u],w[2*u+1]);
}
pii get(int u,int start,int end,int l,int r) {
	if(l>end || r<start) return {n+5,0};
	if(start <= l && r <= end) {
		return w[u];
	}
	int mid=(l+r)/2;
	return min(get(2*u,start,end,l,mid),get(2*u+1,start,end,mid+1,r));
}
main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>D>>t;
	
	for(int i=1;i<=n;i++) {
		cin >> a[i];
		
		// a[j]  - j < t - i
		
	} 	
	build(1,1,n);
	for(int i=1;i<=n;i++){
		int l = 1, r =i,ind = 0;
		while(l<=r){
			int mid=(l+r)/2;
			if(getans(1,mid,i,1,n) <= t-i) {
				ind = mid;
				l = mid + 1;
			}
			else r = mid - 1; 
		}	
		if(ind) ans++;
		if(ind && ind!=i)  { //cout<<ind<<" "<<i<<endl;
			update(1,ind+1,i,1,n,1);
			insert(1,i,1,n,ind+1,i);
		}
		else  {
			insert(1,i,1,n,n+1,i);
		}
	}  
	int cnt  = 0;
	while(tr[1].f && D) {
		int c = tr[1].s; D--; ans -= tr[1].f; //cout<<c<<endl;
		while(get(1,1,c,1,n).f <=  c) { cnt++;// cout<<get(1,1,c,1,n).f <<" "<<get(1,1,c,1,n).s<<endl;
			if(cnt > n) {
				cout<<"??";
				return 0;
			}
			pair<int,int> g = get(1,1,c,1,n);
			insert(1,g.s,1,n,n+1,g.s);
			update(1,g.f,g.s,1,n,-1); 
		}
	} 
	cout<<ans;
}

Compilation message (stderr)

prison.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main(){
      | ^~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20