Submission #1298925

#TimeUsernameProblemLanguageResultExecution timeMemory
1298925nghiaxtoneriJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
21 ms6932 KiB
#include <bits/stdc++.h>
#define int long long 
#define endl '\n'

using namespace std;

const int maxn = 2e5 + 5;
const int inf = 1e18;

int change(char ch){
    if (ch == 'J') return 1;
    if (ch == 'O') return 2;
    if (ch == 'I') return 3;
    return 0;
}

int pre[maxn][4], n, k;
string s;

int sech(int l, int r, int type, int val){
    int res = 0;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (pre[mid][type] >= val){
            res = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return res;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    cin >> s;
    s = '$' + s;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= 3; j++) pre[i][j] = pre[i - 1][j];
        pre[i][change(s[i])]++;
    }

    int ans = inf;

    for (int i = 1; i <= n; i++){
        int lastJ = sech(1, n, 1, pre[i - 1][1] + k);
        if (!lastJ or lastJ > n) continue;

        int lastO = sech(lastJ, n, 2, pre[lastJ - 1][2] + k);
        if (!lastO or lastO > n) continue;

        int lastI = sech(lastO, n, 3, pre[lastO - 1][3] + k);
        if (!lastI or lastI > n) continue;

        ans = min(ans, lastI - i + 1 - 3 * k);
    }

    cout << (ans == inf ? -1 : ans);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...