Submission #541996

#	Time	Username	Problem	Language	Result	Execution time	Memory
541996		skittles1412	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2027 ms	254612 KiB

prison

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

template<bool mn>
struct ST {
	int n;
	vector<int> arr, lazy;
	vector<pair<int, int>> v;

	ST(int n) : ST(vector<int>(n)) {}
	ST(const vector<int>& arr) : n(sz(arr)), arr(arr), lazy(4 * n), v(4 * n) {
		build(1, 0, n - 1);
	}
	
	template <typename T>
	T op(const T &a, const T &b) const {
		if (mn) {
			return min(a, b);
		}
		return max(a, b);
	}

	void build(int o, int l, int r) {
		if (l == r) {
			v[o] = {arr[l], l};
		} else {
			int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
			build(lc, l, mid);
			build(rc, mid + 1, r);
			v[o] = op(v[lc], v[rc]);
		}
	}

	void update(int o, int l, int r, int ql, int qr, int x) {
		if (ql <= l && r <= qr) {
			v[o].first += x;
			lazy[o] += x;
		} else {
			int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
			if (ql <= mid) {
				update(lc, l, mid, ql, qr, x);
			}
			if (mid < qr) {
				update(rc, mid + 1, r, ql, qr, x);
			}
			v[o] = op(v[lc], v[rc]);
			v[o].first += lazy[o];
		}
	}

	pair<int, int> query(int o, int l, int r, int ql, int qr) const {
		if (ql <= l && r <= qr) {
			return v[o];
		} else {
			int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
			pair<int, int> ans {int(mn ? 1e9 : -1e9), -1};
			if (ql <= mid) {
				ans = op(ans, query(lc, l, mid, ql, qr));
			}
			if (mid < qr) {
				ans = op(ans, query(rc, mid + 1, r, ql, qr));
			}
			ans.first += lazy[o];
			return ans;
		}
	}

	void set(int ind, int x) {
		update(1, 0, n - 1, ind, ind, x - arr[ind]);
		arr[ind] = x;
	}

	void add(int l, int r, int x) {
		update(1, 0, n - 1, l, r, x);
	}

	pair<int, int> query(int l, int r) const {
		return query(1, 0, n - 1, l, r);
	}
};

void solve() {
	int n, d, t;
	cin >> n >> d >> t;
	int arr[n];
	for (auto& a : arr) {
		cin >> a;
	}
	int ans = 0;
	vector<int> start(n, n);
	vector<pair<int, int>> st, segs;
	for (int i = 0; i < n; i++) {
		if (t < arr[i]) {
			while (sz(st) && st.back().second < i) {
				st.pop_back();
			}
			if (sz(st)) {
				start[i - 1] = st.back().first;
				segs.emplace_back(st.back().first, i - 1);
			}
		} else {
			ans++;
			st.emplace_back(i, i + t - arr[i]);
		}
	}
	ST<false> cnts(n);
	ST<true> sstarts(start);
	for (auto& [l, r] : segs) {
		dbg(l, r);
		cnts.add(l, r, 1);
	}
	ans += sz(segs);
	for (int i = 0; i < d; i++) {
		int ci = cnts.query(0, n - 1).second;
		dbg(ci);
		while (true) {
			auto [l, r] = sstarts.query(ci, n - 1);
			dbg(l, r);
			if (l <= ci && ci <= r) {
				ans--;
				sstarts.set(r, n);
				cnts.add(l, r, -1);
			} else {
				break;
			}
		}
	}
	cout << ans << endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

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