Submission #754160

#	Time	Username	Problem	Language	Result	Execution time	Memory
754160		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	14 ms	5536 KiB

ho_t2

//srand(time(0)) - always changing
//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long

typedef unsigned long long ull;
typedef long long ll;

using namespace std;
using namespace __gnu_pbds;

const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
const int P = 911;
const ll INF = 1e18;

int gcd(int a, int b) {
	while (b) {
		a %= b;
		swap (a, b);
	}
	return a;
}

ll __sqrt(ll x) {
	ll result = 0;
	for (ll k = 1ll << 30; k != 0; k >>= 1) {
		if ((result + k) * (result + k) <= x) {
			result += k;
		}
	}
	return result;
}

int pj[N], po[N], pi[N];

void solve() {
	int n, k, ans = INF;
	string s;
	cin >> n >> k >> s;
	s = "*" + s;
	for (int i = 1; i <= n; i++) {
		pj[i] = pj[i - 1] + (s[i] == 'J');
		po[i] = po[i - 1] + (s[i] == 'O');
		pi[i] = pi[i - 1] + (s[i] == 'I');
	}
	for (int i = 1; i <= n; i++) {
		if (s[i] != 'J') continue;
		if (pj[n] - pj[i - 1] < k) break;
		int l = i, r = n;
		while (l <= r) {
			int m = l + r >> 1;
			if (pj[m] - pj[i - 1] < k) l = m + 1;
			else r = m - 1;
		}
		int A = l;
		l = A + 1;
		r = n;
		if (po[n] - po[A] < k) break;
		while (l <= r) {
			int m = l + r >> 1;
			if (po[m] - po[A] < k) l = m + 1;
			else r = m - 1;
		}
		int B = l;
		l = B + 1;
		r = n;
		if (pi[n] - pi[B] < k) break;
		while (l <= r) {
			int m = l + r >> 1;
			if (pi[m] - pi[B] < k) l = m + 1;
			else r = m - 1;
		}
		ans = min(ans, l - i + 1 - (k * 3));
//		cout << ' ' << i << ' ' << l << '\n';
	}
	if (ans == INF) ans = -1;
	cout << ans;
}

const bool Cases = 0;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int TT = 1;
	if (Cases) cin >> TT;
	while (TT--) {
		solve();
	}
}

Compilation message (stderr)

ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |    int m = l + r >> 1;
      |            ~~^~~
ho_t2.cpp:77:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |    int m = l + r >> 1;
      |            ~~^~~
ho_t2.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |    int m = l + r >> 1;
      |            ~~^~~

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