Submission #1325996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325996		Agageldi	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	27 ms	9948 KiB

ho_t2

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

#define int long long
#define N 500005

const int inf = 1e18;

int k, n, a[N], p[N][5], ans = inf;
string s, g = "JOI";

int32_t main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> k >> s;
    int inx = 0;
    map <char,int> vis;
    for(int j = 0; j < 3; j++) {
        vis[g[j]] = j + 1;
    }
    for(int i = 0; i < n; i++) {
        a[i + 1] = vis[s[i]];
    }
    for(int i = 1; i <= n; i++) {
        p[i][a[i]]++;
        for(int j = 1; j <= 3; j++) {
            p[i][j] += p[i - 1][j];
        }
    }
    int b = 1, O = 0, J = 0, I = 0;
    for(int i = 1; i <= n; i++) {
        O += (a[i] == 2);
        while(b <= i && O - (a[b] == 2) >= k) {
            O -= (a[b] == 2);
            b++;
        }
        int l = 1, r = b - 1, x1 = 0, x2 = 0;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(p[b - 1][1] - p[mid - 1][1] >= k) {
                l = mid + 1;
                x1 = mid;
            }
            else r = mid - 1;
        }
        l = i + 1, r = n;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(p[mid][3] - p[i][3] >= k) {
                r = mid - 1;
                x2 = mid;
            }
            else l = mid + 1;
        }
        if(!x1 || !x2) continue;
        ans = min(ans, ((b - 1) - x1 + 1) + (i - b + 1) + (x2 - (i + 1) + 1) - (3 * k));
    }
    // cout << ans << '\n';
    cout << (ans == inf ? -1 : ans) << '\n';
    return 0;
}

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