Submission #660033

#	Time	Username	Problem	Language	Result	Execution time	Memory
660033		ymm	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1784 ms	119016 KiB

prison

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1<<21;
int a[N];
int n, d, t;

int fen[N];
void fen_add(int i, int x)
{
	++i;
	while (i < N) {
		fen[i] += x;
		i += i&-i;
	}
}
int fen_get(int r)
{
	int ans = 0;
	while (r) {
		ans += fen[r];
		r -= r&-r;
	}
	return ans;
}
int fen_get(int l, int r) { return fen_get(r) - fen_get(l); }

int l_of[N];
int r_of[N];
int mn_of[N];
int nxt_less[N];

int merge(int l, int m, int r, bool dry)
{
	int i = mn_of[l];
	int j = min(r, nxt_less[i]);
	// t - x == a[i]
	int pnt = t - a[i] + 1;
	pnt = min(j, pnt);
	pnt = max(m, pnt);
	int pre_good = fen_get(m, pnt);
	if (!dry)
		fen_add(m, (pnt - m) - pre_good);
	return (pnt - m) - pre_good;
}

int main(int argc, char **argv)
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> d >> t;
	int lst = 1e9+10;
	Loop (i,0,n) {
		cin >> a[i];
		a[i] -= i;
	}
	vector<int> st;
	LoopR (i,0,n) {
		while (st.size() && a[i] < a[st.back()])
			st.pop_back();
		nxt_less[i] = st.size()? st.back(): n;
		st.push_back(i);
	}
	Loop (i,0,n) {
		r_of[i] = i+1;
		l_of[i+1] = i;
		mn_of[i] = i;
	}
	l_of[0] = n+1;
	r_of[n] = n+1;
	l_of[n+1] = n+1;
	r_of[n+1] = n+1;
	int ans = 0;
	Loop (i,0,n) {
		int tmp = a[i]+i <= t;
		ans += tmp;
		fen_add(i, tmp);
	}
	priority_queue<pair<int, pii>> pq;
	Loop (i,1,n) {
		int x = merge(i-1, i, i+1, 1);
		pq.push({-x, {i-1, i+1}});
	}
	LoopR (_,d,n-1) {
		assert(pq.size());
		auto [x, foo] = pq.top();
		auto [l, r] = foo;
		pq.pop();
		x = -x;
		int m = r_of[l];
		if (m == n+1 || m != l_of[r]) {
			++_;
			continue;
		}
		ans += x;
		merge(l, m, r, 0);
		r_of[l] = r;
		l_of[r] = l;
		l_of[m] = r_of[m] = n+1;
		if (a[mn_of[l]] >= a[mn_of[m]])
			mn_of[l] = mn_of[m];
		int l2 = l_of[l];
		int r2 = r_of[r];
		if (l2 != n+1) {
			int x = merge(l2, l, r, 1);
			pq.push({-x, {l2, r}});
		}
		if (r2 != n+1) {
			int x = merge(l, r, r2, 1);
			pq.push({-x, {l, r2}});
		}
	}
	cout << ans << '\n';
}

Compilation message (stderr)

prison.cpp: In function 'int main(int, char**)':
prison.cpp:56:6: warning: unused variable 'lst' [-Wunused-variable]
   56 |  int lst = 1e9+10;
      |      ^~~

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