Submission #465338

#	Time	Username	Problem	Language	Result	Execution time	Memory
465338		AmShZ	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1993 ms	318864 KiB

prison

//khodaya khodet komak kon
#pragma GCC optimize("O2")
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 2e6 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 1e9 + 7;//998244353;
const int base = 257;

int n, D, T, a[xn], L[xn], ans = - 1, stm[xn];
int par[xn], ftm[xn], TM, m = 1, P[xn], lazy[xn << 2];
pii seg[xn << 2];
set <int> st;
vector <int> Q[xn], adj[xn];
bool mark[xn];

void solve(int v = 1, int l = 1, int r = n + 1){
	if (r <= l)
		return;
	int pt = r - 1;
	while (l <= pt){
		if (L[pt] == pt || !L[pt]){
			ans += !L[pt];
			-- pt;
			continue;
		}
		adj[v].push_back(++ m);
		solve(m, L[pt], pt);
		pt = L[pt] - 1;
	}
}
void preDFS(int v){
	P[TM] = v;
	stm[v] = TM ++;
	for (int u : adj[v])
		par[u] = v, preDFS(u);
	ftm[v] = TM;
}
void shift(int id, int l, int r){
	if (!lazy[id])
		return;
	seg[id].A += lazy[id];
	if (1 < r - l){
		lazy[lc] += lazy[id];
		lazy[rc] += lazy[id];
	}
	lazy[id] = 0;
}
void update(int id, int l, int r, int ql, int qr, int val){
	shift(id, l, r);
	if (qr <= l || r <= ql || qr <= ql)
		return;
	if (ql <= l && r <= qr){
		lazy[id] += val;
		shift(id, l, r);
		return;
	}
	int mid = l + r >> 1;
	update(lc, l, mid, ql, qr, val);
	update(rc, mid, r, ql, qr, val);
	seg[id] = max(seg[lc], seg[rc]);
}
void build(int id, int l, int r){
	if (r - l == 1){
		seg[id].B = P[l];
		return;
	}
	int mid = l + r >> 1;
	build(lc, l, mid), build(rc, mid, r);
	seg[id] = seg[lc];
}

int main(){
	fast_io;

	cin >> n >> D >> T;
	if (n == 1){
		if (a[1] <= T)
			kill(1);
		kill(0);
	}
	for (int i = 1; i <= n; ++ i){
		cin >> a[i];
		if (a[i] <= T){
			st.insert(- i);
			Q[min(n, i + T - a[i])].push_back(i);
		}
		if (SZ(st))
			L[i] = - *st.begin();
		for (int x : Q[i])
			st.erase(- x);
	}
	solve();
	preDFS(1);
	build(1, 0, TM);
	for (int i = 1; i <= m; ++ i)
		update(1, 0, TM, stm[i], ftm[i], 1);
	while (D --){
		int v = seg[1].B;
		if (seg[1].A < 1)
			break;
		while (!mark[v] && v){
			mark[v] = true;
			++ ans;
			update(1, 0, TM, stm[v], ftm[v], - 1);
			v = par[v];
		}
	}
	cout << n - ans << endl;

	return 0;
}

Compilation message (stderr)

prison.cpp: In function 'void update(int, int, int, int, int, int)':
prison.cpp:85:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |  int mid = l + r >> 1;
      |            ~~^~~
prison.cpp: In function 'void build(int, int, int)':
prison.cpp:95:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |  int mid = l + r >> 1;
      |            ~~^~~

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