Submission #1015221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015221		aufan	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	34 ms	12060 KiB

ho_t2

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int inf = 1e9;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, k;
        cin >> n >> k;

        string s;
        cin >> s;
        s = '?' + s;

        vector<vector<int>> pref(n + 1, vector<int>(3));
        for (int i = 1; i <= n; i++) {
                pref[i] = pref[i - 1];
                if (s[i] == 'J') pref[i][0] += 1;
                if (s[i] == 'O') pref[i][1] += 1;
                if (s[i] == 'I') pref[i][2] += 1;
        }

        int p = 1, ans = inf;
        for (int i = 1; i <= n; i++) {
                while (p + 1 <= n && pref[p][1] - pref[i - 1][1] < k) p += 1;
                if (pref[p][1] - pref[i - 1][1] < k) break;

                int lf = 1, rg = i - 1, pl = -1;
                while (lf <= rg) {
                        int md = (lf + rg) / 2;

                        if (pref[i - 1][0] - pref[md - 1][0] >= k) {
                                pl = md;
                                lf = md + 1;
                        } else {
                                rg = md - 1;
                        }
                }

                if (pl == -1) continue;

                int pr = -1;
                lf = p + 1, rg = n;
                while (lf <= rg) {
                        int md = (lf + rg) / 2;

                        if (pref[md][2] - pref[p][2] >= k) {
                                pr = md;
                                rg = md - 1;
                        } else {
                                lf = md + 1;
                        }
                }

                if (pr == -1) continue;

                ans = min(ans, (pr - pl + 1) - 3 * k);
        }
        
        cout << (ans == inf ? -1 : ans) << '\n';
        
        return 0;
}

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