Submission #1228257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228257		wedonttalkanymore	JJOOII 2 (JOI20_ho_t2)	C++20	0 / 100	0 ms	328 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define pii pair <ll, ll>
#define fi first
#define se second

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];
ll up[N][lim + 1];
ll cnt[N][lim + 1][5];

int find_next(int u, int type) {
	ll have = k - 1;
	for (int i = lim; i >= 0; i--) {
//		cout << u << '\n';
		int x = up[u][i];
		int tmp = cnt[u][i][type];
		if (tmp <= have && up[u][i] > 0 && up[u][i] <= n) {
//			cout << x << ' ' << tmp << '\n';
			have -= tmp;
			u = up[u][i];
		}
	}
	char what[4] = {'?', 'J','O','I'};
	if (have == 0 && u >= 1 && u <= n && s[u] == what[type]) return u;
	else return -1;
}
bool check(int mid) {
	bool ok = false;
	for (int j = 0; j <= n; j = nxt[j].j) {
		if (j == 0) continue;
//		cout << j << ' ';
		int First = find_next(j, 1); // k con J
//		if (j == 2) cout << First << ' ';
		if (First == -1) break;
		int o = nxt[First].o; // con o dau tien dang sau
		int Second = find_next(o, 2); // k con O
//		if (j == 2) cout << Second << ' ';
		if (Second == -1) break;
		int i = nxt[Second].i;
		int Third = find_next(i, 3); // k con I
//		if (j == 2) cout << Third << ' ';
		if (Third == -1) break;
		if ((Third - j + 1) - 3 * k <= mid) ok = true;
	}
	return ok;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k >> s;
	s = "#" + s;
	int nxt_j = n + 1, nxt_o = n + 1, nxt_i = n + 1;
	for (int i = n; i >= 1; i--) {
		nxt[i] = {nxt_j, nxt_o, nxt_i};
		if (s[i] == 'J') nxt_j = i;
		else if (s[i] == 'O') nxt_o = i;
		else nxt_i = i;
	}
//	cout << 1 << '\n';
	nxt[0] = {nxt_j, nxt_o, nxt_i};
//	cout << 1 << '\n';
//	for (int i = 1; i <= n; i++) cout << nxt[i].j << ' ' << nxt[i].o << ' ' << nxt[i].i << '\n';
	for (int i = 1; i <= n; i++) {
		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;
		int x = up[i][0];
		cnt[i][0][1] = (x && s[x] == 'J');
		cnt[i][0][2] = (x && s[x] == 'O');
		cnt[i][0][3] = (x && s[x] == 'I');
	}
//	cout << 1 << '\n';
//	for (int i = 1; i <= n; i++) cout << up[i][0] << '\n';
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= lim; j++) {
//			if (i == 1 && j == 1) cout << up[i][j - 1] << ' ' << up[up[i][j - 1]][j - 1] << '\n';
			up[i][j] = up[up[i][j - 1]][j - 1];
			for (int k = 1; k <= 3; k++) {
				cnt[i][j][k] = cnt[up[i][j - 1]][j - 1][k] + cnt[i][j - 1][k];
			}
		}
	}
//	cout << 1 << '\n';
//	cout << cnt[1][lim][2] << '\n';
//	cout << s[1] << '\n';
//	cout << up[1][0] << '\n';
//	cout << up[1][1] << '\n';

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

9 3
JJJOOOIII
*/

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