Submission #1228286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228286		wedonttalkanymore	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	502 ms	193292 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

const ll N = 2e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19;

int n, k;
string s;

struct item {
	int j, o, i;
} nxt[N + 2];

int up[N + 2][lim + 1];
int cnt[N + 2][lim + 1][5];
char whatc[4] = {'?', 'J', 'O', 'I'};

int find_next(int u, int type) {
	int have = k;
	if (u <= n && s[u] == whatc[type]) {
		have--;
		if (have == 0) return u;
	}
	for (int j = lim; j >= 0; j--) {
		int v = up[u][j];
		if (v <= n && cnt[u][j][type] < have) {
			have -= cnt[u][j][type];
			u = v;
		}
	}
	u = up[u][0];
	if (u <= n && s[u] == whatc[type] && have == 1) return u;
	return -1;
}

bool check(int mid) {
	for (int j = nxt[0].j; j <= n; j = nxt[j].j) {
		int First = find_next(j, 1);
		if (First == -1) return false;
		int Second = find_next(nxt[First].o, 2);
		if (Second == -1) return false;
		int Third = find_next(nxt[Second].i, 3);
		if (Third == -1) return false;
		if ((Third - j + 1) - 3 * k <= mid) return true;
	}
	return false;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> k >> s;
	s = "#" + s;

	int nj = n + 1, no = n + 1, ni = n + 1;
	for (int i = n; i >= 1; i--) {
		nxt[i] = {nj, no, ni};
		if (s[i] == 'J') nj = i;
		else if (s[i] == 'O') no = i;
		else ni = i;
	}
	nxt[0] = {nj, no, ni};
	nxt[n + 1] = {n + 1, n + 1, n + 1};

	for (int i = 0; i <= n + 1; i++) {
		if (i >= 1 && i <= n) {
			if (s[i] == 'J') up[i][0] = nxt[i].j;
			else if (s[i] == 'O') up[i][0] = nxt[i].o;
			else up[i][0] = nxt[i].i;
		} else up[i][0] = i;

		for (int t = 1; t <= 3; t++) cnt[i][0][t] = 0;

		if (i >= 1 && i <= n) {
			int x = up[i][0];
			if (x <= n) {
				cnt[i][0][1] = (s[x] == 'J');
				cnt[i][0][2] = (s[x] == 'O');
				cnt[i][0][3] = (s[x] == 'I');
			}
		}
	}

	for (int j = 1; j <= lim; j++) {
		for (int i = 0; i <= n + 1; i++) {
			int x = up[i][j - 1];
			up[i][j] = up[x][j - 1];
			for (int t = 1; t <= 3; t++) {
				cnt[i][j][t] = cnt[i][j - 1][t] + cnt[x][j - 1][t];
			}
		}
	}

	int l = 0, r = n, ans = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87