Submission #537297

#	Time	Username	Problem	Language	Result	Execution time	Memory
537297		skittles1412	The short shank; Redemption (BOI21_prison)	C++17	55 / 100	878 ms	524288 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> v, lazy;

	explicit ST(int n) : n(n), v(4 * n, 1e9), lazy(4 * n) {}

	void update(int o, int l, int r, int ql, int qr, int x) {
		if (ql <= l && r <= qr) {
			v[o] += 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] = min(v[lc], v[rc]) + lazy[o];
		}
	}

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

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

	int query() const {
		return v[1];
	}

	int get(int ind) {
		return query(ind, ind);
	}

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

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

	void set(int ind, int x) {
		update(ind, ind, x - get(ind));
	}
};

struct DS {
	vector<int> arr;

	explicit DS(int n) : arr(n, 1e9) {}

	void set(int ind, int x) {
		arr[ind] = x;
	}

	int get(int ind) const {
		return arr[ind];
	}

	void update(int l) {
		for (int i = l; i < sz(arr); i++) {
			arr[i]++;
		}
	}

	int query() const {
		return *min_element(begin(arr), end(arr));
	}
};

void solve() {
	int n, m, rt;
	cin >> n >> m >> rt;
	int in[n];
	for (auto& a : in) {
		cin >> a;
	}
	int arr[n];
	for (int i = 0; i < n; i++) {
		arr[i] = max(-1, rt - in[i]);
	}
	vector<ST> dp;
	for (int i = 0; i <= m; i++) {
		dp.emplace_back(n + 1);
		dp.back().set(n, 0);
	}
	vector<int> good;
	for (int i = n - 1; i >= 0; i--) {
		if (arr[i] >= 0) {
			while (sz(good) && good.back() <= i + arr[i]) {
				int x = good.back();
				dbg(x);
				good.pop_back();
				for (auto& a : dp) {
					a.update(x + 1);
				}
			}
		} else {
			good.push_back(i);
		}
		for (int j = 0; j < m; j++) {
			int ans = dp[j + 1].query();
			dbg(j, i, ans);
			dp[j].set(i, ans);
		}
		dp[m].set(i, dp[m].get(n));
	}
	int ans = 0;
	for (auto& a : arr) {
		ans += a >= 0;
	}
	cout << ans + dp[0].get(0) << 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: 0 / 25
• Subtask 6: 0 / 20