Submission #1244877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244877		drakozs	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	37 ms	5336 KiB

ho_t2

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define MOD 998244353
#define MAXN 2e5
#define SIZE 314

using namespace std;

int solve(string &s, int start, int n, int k, vector<ll> &J, vector<ll> &O, vector<ll> &I){
	int curr = start;
	int l = curr, r = n - 1, mid;
	int bestPos = -1;
	while(l <= r){
		mid = (r - l) / 2 + l;
		ll count = J[mid + 1] - J[curr];
		if (count >= k){
			bestPos = mid;
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	if (bestPos == -1) return -1;
	curr = bestPos + 1;
	
	
	l = curr, r = n - 1;
	bestPos = -1;
	while(l <= r){
		mid = (r - l) / 2 + l;
		ll count = O[mid + 1] - O[curr];
		if (count >= k){
			bestPos = mid;
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	if (bestPos == -1) return -1;
	curr = bestPos + 1;
	
	l = curr, r = n - 1;
	bestPos = -1;
	while(l <= r){
		mid = (r - l) / 2 + l;
		ll count = I[mid + 1] - I[curr];
		if (count >= k){
			bestPos = mid;
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	if (bestPos == -1) return -1;
	curr = bestPos + 1;
	
	return curr - start;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	vector<ll> J(n + 1), O(n + 1), I(n + 1);
	J[0] = O[0] = I[0] = 0;
	for (int i = 0; i < n; i++){
		J[i + 1] = J[i];
		O[i + 1] = O[i];
		I[i + 1] = I[i];
		if (s[i] == 'J') J[i+1]++;
		else if (s[i] == 'O') O[i+1]++;
		else I[i+1]++;
	}
	if (solve(s, 0, n, k, J, O, I) == -1){
		cout << "-1\n";
		return 0;
	}
	ll ans = n;
	for (int i = 0; i < n; i++){
		ll curr = solve(s, i, n, k, J, O, I);
		if (curr != -1 && curr < ans) ans = curr;
	}
	cout << ans - 3 * k << "\n";
	
	return 0;
}

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