Submission #734217

#	Time	Username	Problem	Language	Result	Execution time	Memory
734217		pavement	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1972 ms	524288 KiB

prison

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//~ #define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, D, T, ans, t[2000005], l[2000005];
bool seen[2000005];
stack<ii> st;

struct node *root;

struct node {
	node *left, *right;
	int S, E, pv;
	ii val;
	vector<int> vec;
	node(int _s, int _e) : S(_s), E(_e), pv(0) {
		if (S == E) {
			val = mp(0, S);
			return;
		}
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
		val = max(left->val, right->val);
	}
	void prop() {
		if (S == E || !pv) return;
		left->val.first += pv;
		left->pv += pv;
		right->val.first += pv;
		right->pv += pv;
		pv = 0;
	}
	void upd(int l, int r, int v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			val.first += v;
			pv += v;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		val = max(left->val, right->val);
	}
	void add(int l, int r, int idx) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			vec.pb(idx);
			return;
		}
		left->add(l, r, idx);
		right->add(l, r, idx);
	}
	void get_all(int p) {
		for (auto i : vec) {
			if (seen[i]) continue;
			seen[i] = 1;
			root->upd(l[i], i, -1);
		}
		vec.clear();
		if (S == E) return;
		int M = (S + E) >> 1;
		prop();
		if (p <= M) left->get_all(p);
		else right->get_all(p);
	}
};

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> D >> T;
	for (int i = 1; i <= N; i++) {
		cin >> t[i];
	}
	root = new node(1, N);
	for (int i = 1; i <= N; i++) {
		// find max j such that
		// t[j] + i - j <= T
		// t[j] - j <= T - i
		while (!st.empty() && st.top().first >= t[i] - i) st.pop();
		st.emplace(t[i] - i, i);
		while (!st.empty() && st.top().first > T - i) st.pop();
		if (st.empty()) ans--;
		else if (st.top().second + 1 <= i) {
			l[i] = st.top().second + 1;
			root->upd(l[i], i, 1);
			root->add(l[i], i, i);
		}
	}
	ans += N;
	while (D--) {
		auto cur = root->val;
		if (cur.first == 0) break;
		ans -= cur.first;
		root->get_all(cur.second);
	}
	cout << ans << '\n';
}

Compilation message (stderr)

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

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