Submission #1104287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104287		zephyrion	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	153 ms	3548 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
 
    vector<int> prefix_j(n + 1), prefix_o(n + 1), prefix_i(n + 1);
 
    for (int i = 0; i < n; i++) {
        prefix_j[i + 1] = prefix_j[i] + (s[i] == 'J');
        prefix_o[i + 1] = prefix_o[i] + (s[i] == 'O');
        prefix_i[i + 1] = prefix_i[i] + (s[i] == 'I');
    }
 
    int ans = n + 1;
 
    for (int i = k; i <= n - 2 * k; i++) {
        if (prefix_j[i] < k || prefix_o[n] - prefix_o[i] < k) {
            continue;
        }
 
        auto check = [&](int j) {
            if (prefix_o[j] - prefix_o[i] < k) {
                return -1;
            }
            int l = j, r = n + 1;
            while (l + 1 < r) {
                int mid = (l + r) / 2;
                if (prefix_i[mid] - prefix_i[j] >= k) {
                    r = mid;
                } else {
                    l = mid;
                }
            }
            return r <= n ? r : -2;
        };
 
        int l = i, r = n + 1;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (~check(mid)) {
                r = mid;
            } else {
                l = mid;
            }
        }
 
        if (r <= n) {
            r = check(r);
            int L = 0, R = i + 1;
            while (L + 1 < R) {
                int mid = (L + R) / 2;
                if (prefix_j[i] - prefix_j[mid - 1] >= k) {
                    L = mid;
                } else {
                    R = mid;
                }
            }
            if (r > 0) {
                ans = min(ans, r - L + 1 - 3 * k);
            }
        }
    }
 
    cout << (ans > n ? -1 : ans) << "\n";
    return 0;
}

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