Submission #542000

#	Time	Username	Problem	Language	Result	Execution time	Memory
542000		skittles1412	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1822 ms	158928 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())

struct ST {
	int n;
	vector<int> lazy;
	vector<long> v;

	ST(int n) : n(n), lazy(4 * n), v(4 * n) {
		build(1, 0, n - 1);
	}

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

	void update(int o, int l, int r, int ql, int qr, bool sub) {
		if (ql <= l && r <= qr) {
			if (sub) {
				v[o] -= long(1) << 30;
				lazy[o]--;
			} else {
				v[o] += long(1) << 30;
				lazy[o]++;
			}
		} else {
			int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
			if (ql <= mid) {
				update(lc, l, mid, ql, qr, sub);
			}
			if (mid < qr) {
				update(rc, mid + 1, r, ql, qr, sub);
			}
			v[o] = max(v[lc], v[rc]);
			v[o] += long(lazy[o]) << 30;
		}
	}

	long 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;
			long ans = -1;
			if (ql <= mid) {
				ans = max(ans, query(lc, l, mid, ql, qr));
			}
			if (mid < qr) {
				ans = max(ans, query(rc, mid + 1, r, ql, qr));
			}
			ans += long(lazy[o]) << 30;
			return ans;
		}
	}

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

	pair<int, int> query(int l, int r) const {
		long ans = query(1, 0, n - 1, l, r);
		return {ans >> 30, ans & ((1 << 30) - 1)};
	}
};

namespace st1 {

const int maxn = 1 << 21;

pair<int, int> v[maxn * 2];

void set(int ind, int x) {
	ind += maxn;
	v[ind].first = x;
	while (ind > 1) {
		v[ind >> 1] = min(v[ind], v[ind ^ 1]);
		ind >>= 1;
	}
}

pair<int, int> query(int l, int r) {
	pair<int, int> ans {int(1e9), -1};
	l += maxn;
	r += maxn;
	while (l < r) {
		if (l & 1) {
			ans = min(ans, v[l++]);
		}
		if (r & 1) {
			ans = min(ans, v[--r]);
		}
		l >>= 1;
		r >>= 1;
	}
	return ans;
}

void init(const vector<int>& arr) {
	fill(begin(v), end(v), pair<int, int> {int(1e9), -1});
	for (int i = 0; i < maxn; i++) {
		v[i + maxn].second = i;
	}
	for (int i = 0; i < sz(arr); i++) {
		set(i, arr[i]);
	}
}

}  // namespace st1

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 cnts(n);
	st1::init(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] = st1::query(ci, n - 1);
			dbg(l, r);
			if (l <= ci && ci <= r) {
				ans--;
				st1::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: 20 / 20