Submission #469349

#	Time	Username	Problem	Language	Result	Execution time	Memory
469349		Drew_	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	321 ms	3052 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX = 2e5 + 69;
constexpr int inf = 1e9 + 69;

int n, k;
char s[MAX];
int bit[3][MAX];

inline void add(int y, int x, int val)
{
	for (int i = x; i < MAX; i += (i & -i))
		bit[y][i] += val;
}

inline int sum(int y, int x)
{
	int res = 0;
	for (int i = x; i > 0; i -= (i & -i))
		res += bit[y][i];
	return res;
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k >> (s+1);

	for (int i = 1; i <= n; ++i)
	{
		if (s[i] == 'J') add(0, i, 1);
		if (s[i] == 'O') add(1, i, 1);
		if (s[i] == 'I') add(2, i, 1);
	}

	int res = inf;
	for (int i = 0; i <= n; ++i)
	{
		int x = i+1;
		for (int y = 0; y < 3; ++y)
		{
			int l = x, r = n+1;
			while (l < r)
			{
				int mid = (l + r) >> 1;
				if (sum(y, mid) - sum(y, x-1) < k) l = mid + 1;
				else r = mid;
			}
			x = l;
		}
		if (x == n+1) break;

		res = min(res, x-i - 3*k);
	}
	cout << (res == inf ? -1 : res) << '\n';

	return 0;
}

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