Submission #1287389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287389		peanut	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	28 ms	3572 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 5;
int n, k;
int a[maxn];
int pfs[maxn][3];
int bs(int l, int idx)
{
    int lo = l, hi = n+1;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (pfs[mid][idx] - pfs[l-1][idx] >= k) hi = mid;
        else lo = mid + 1;
    }
    return (lo >= n+1 ? -1 : lo);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        char c; cin >> c;
        for (int j = 0; j < 3; ++j) pfs[i][j] = pfs[i-1][j];
        if (c == 'J') a[i] = 0;
        else if (c == 'O') a[i] = 1;
        else a[i] = 2;
        pfs[i][a[i]]++;
    }

    int ops = INT_MAX;
    for (int i = 1; i <= n; ++i)
    {
        int pos1 = bs(i, 0);
        int pos2 = bs(pos1+1, 1);
        int pos3 = bs(pos2+1, 2);
//        cout << pos1 << ' ' << pos2 << ' ' << pos3 << '\n';
        if (pos1 != -1 && pos2 != -1 && pos3 != -1) ops = min(ops, pos3-i+1-3*k);
    }
    cout << (ops == INT_MAX ? -1 : ops);
    return 0;
}

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