Submission #482403

#	Time	Username	Problem	Language	Result	Execution time	Memory
482403		pnm1384	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	8 ms	332 KiB

prison

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define F first
#define S second

const int N = 2e6 + 20, inf = 1e8;
int a[N];
stack<int> st;
vector<pair<int, int>> vt;
pair<int, int> seg[N << 2]; //  <mx, ind>
int ans[N];
int n, D, T;

bool compa(pair<int, int> p1, pair<int, int> p2) {return p1.S - p1.F < p2.S - p2.F;}

void build(int u = 1, int s = 0, int e = N)
{
	if (e - s < 2)
	{
		seg[u] = {0, s};
		return;
	}
	int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
	build(lc, s, mid); build(rc, mid, e);
	seg[u] = max(seg[lc], seg[rc]);
	return;
}

void add(int ind, int x, int u = 1, int s = 0, int e = N)
{
	if (e - s < 2)
	{
		seg[u].F += x;
		return;
	}
	int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
	if (ind < mid)
		add(ind, x, lc, s, mid);
	else
		add(ind, x, rc, mid, e);

	seg[u] = max(seg[lc], seg[rc]);
	return;
}

pair<int, int> get(int l, int r, int u = 1, int s = 0, int e = N)
{
	if (e <= l || r <= s) return {-inf, -inf};
	if (l <= s && r >= e) return seg[u];
	int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
	return max(get(l, r, lc, s, mid), get(l, r, rc, mid, e));
}

void build2(int u = 1, int s = 0, int e = N)
{
	if (e - s < 2)
	{
		if (s < n - 1)
		{
			ans[s] = -seg[u].F;
	//		cout << "              " << s + 1 << "   " << seg[u].F << '\n';
		}
		return;
	}
	int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
	build2(lc, s, mid); build2(rc, mid, e);
	return;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
	cin >> n >> D >> T;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		st.push(i);
		while (!st.empty())
		{
			if (a[st.top()] - st.top() > T - i)
			{
				st.pop();
				continue;
			}
			break;
		}
		if (st.empty()) continue;
		if (st.top() == i) continue;
	//	cout << "                 " << i + 1 << "   " << st.top() << '\n';
		vt.push_back({st.top(), i - 1});
	}
	sort(vt.begin(), vt.end(), compa);
	for (pair<int, int> p : vt)
	{
		int l = p.F, r = p.S;
		int x = get(l, r + 1).S;
	//	cout << "                 " << x + 1 << '\n';
		add(x, 1);
	}
	build2();
	sort(ans, ans + n - 1);
	int bad = 0;
	for (int i = 0; i < min(D, n - 1); i++) bad -= ans[i];
	cout << n - bad;
	return 0;
}

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