Submission #863798

#	Time	Username	Problem	Language	Result	Execution time	Memory
863798		arashMLG	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2016 ms	250436 KiB

prison

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
 
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
 
#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'
 
const int N = 1e6+23, lg = 21;
ll Mod = 1e9+7; //998244353;
 
int n, d, T, t[2*N], ans, seg[5*N], res[2*N], l[2*N];
int lazy[5*N], seg2[5*N];
 
void update2(int ind, int val) {
	if(ind == 0) return;
	if(ind >= (1<<lg)) {
		seg[ind] = val;
	} else {
		seg[ind] = min(seg[2*ind], seg[2*ind+1]);
	}
	update2(ind/2, val);
}
 
int find(int val, int ind=1) {
	if(seg[ind] > val) return 0;
	if(ind >= (1<<lg)) {
		return (ind-(1<<lg)+1);
	}
	if(seg[2*ind+1] <= val) return find(val, 2*ind+1);
	return find(val, 2*ind);
}
 
void pushdown(int ind) {
  if(lazy[ind]==0) return;
	seg[ind] += lazy[ind];
	if(ind < (1<<lg)) {
		lazy[2*ind] += lazy[ind];
		lazy[2*ind+1] += lazy[ind];
	}
	lazy[ind] = 0;
}
 
void update(int l, int r, int val, int ind=1, int lc=1, int rc=(1<<lg)+1) {
	pushdown(ind);
	if(r<=lc || rc<=l) return;
	if(lc>=l && rc<=r) {
		lazy[ind] += val;
		pushdown(ind);
		return;
	}
	int mid = (lc+rc)/2;
	update(l, r, val, 2*ind, lc, mid);
	update(l, r, val, 2*ind+1, mid, rc);
	seg[ind] = max(seg[2*ind], seg[2*ind+1]);
}
 
int query(int ind=1, int lc=1, int rc=(1<<lg)+1) {
	pushdown(ind);
	if(ind >= (1<<lg)) {
		return lc;
	}
	int mid = (lc+rc)/2;
	if(seg[ind] == lazy[2*ind]+seg[2*ind]) {
		return query(2*ind, lc, mid);
	}
	return query(2*ind+1, mid, rc);
}
 
void update3(int ind, int val) {
	if(ind == 0) return;
	if(ind >= (1<<lg)) {
		seg2[ind] = val;
	} else {
		seg2[ind] = (l[seg2[2*ind]]<l[seg2[2*ind+1]] ? seg2[2*ind] : seg2[2*ind+1]);
	}
	update3(ind/2, val);
}
 
int query3(int l2, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) {
	if(lc>=r || l2>=rc) return 0;
	if(lc>=l2 && rc<=r) {
		return seg2[ind];
	}
	int mid = (lc+rc)/2;
	int x = query3(l2, r, 2*ind, lc, mid), y = query3(l2, r, 2*ind+1, mid, rc);
	return (l[x]<l[y] ? x : y);
}
 
int hlp[lg][2*N];
int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);
 
	cin>>n>>d>>T;
	
	l[0] = n+1;
	for(int i=1; i<=n; i++) {cin>>t[i];}
	//fill(seg, seg+5*N, (int)2e9);
 
	for(int i=1; i<=n; i++) {
		//update2(i+(1<<lg)-1, t[i]-i);
		hlp[0][i] = t[i] - i;
		for(int j=1; j<lg; j++) {
			hlp[j][i] = min(hlp[j-1][i], hlp[j-1][max(i-(1<<(j-1)), 1)]);
		}
		int j = i;
		for(int x=lg-1; x>=0; x--) {
			if(j>0 && hlp[x][j] > T-i) {
				j -= (1<<x);
			}
		}
		if(t[j]-j > T-i) {
			j--;
		}
		j = max(j, 0);
		if(j==0 || j == i) {
			l[i] = n+1;
			ans+=(j<i);
		} else {
			l[i] = j+1;
		}
	}
 
	for(int i=1; i<=n; i++) {
		if(l[i] > n) continue;
		update(l[i], i+1, 1);
		update3(i+(1<<lg)-1, i);
	}
 
	for(int i=1; i<=d; i++) {
		int wh = query();
		if(seg[(1<<lg)+wh-1] == 0) break;
		ans += seg[(1<<lg)+wh-1];
		while(true) {
			int ff = query3(wh, n+1);
			if(l[ff] > wh) break;
			update(l[ff], ff+1, -1);
			l[ff] = n+1;
			update3(ff+(1<<lg)-1, ff);
		}
	}
 
	cout<<n-ans<<endl;
 
	return 0;
}

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