Submission #1180433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180433		anteknne	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	20 ms	3088 KiB

ho_t2

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

string s;
const int MAXN = 200 * 1000 + 17;
int sprefj[MAXN];
int sprefo[MAXN];
int sprefi[MAXN];

void dodaj (int i) {
    if (s[i] == 'J') {
        sprefj[i] ++;
    }
    if (s[i] == 'O') {
        sprefo[i] ++;
    }
    if (s[i] == 'I') {
        sprefi[i] ++;
    }
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, K;
    cin >> n >> K >> s;

    s = "#" + s;

    for (int i = 1; i <= n; i ++) {
        sprefj[i] = sprefj[i - 1];
        sprefo[i] = sprefo[i - 1];
        sprefi[i] = sprefi[i - 1];
        dodaj(i);
        //cout << sprefj[i] << "\n";
    }
    sprefj[n + 1] = INT_MAX;
    sprefo[n + 1] = INT_MAX;
    sprefi[n + 1] = INT_MAX;

    int wyn = INT_MAX;

    for (int i = 1; i <= n; i ++) {
        int p = 0, k = n + 1, wj;
        while (p <= k) {
            int sr = (p + k)/ 2;
            if (sprefj[sr] >= sprefj[i - 1] + K) {
                wj = sr;
                k = sr - 1;
            } else {
                p = sr + 1;
            }
        }
        p = 0, k = n + 1;
        int wo;
        while (p <= k) {
            int sr = (p + k)/ 2;
            if (sprefo[sr] >= sprefo[wj - 1] + K) {
                wo = sr;
                k = sr - 1;
            } else {
                p = sr + 1;
            }
        }
        p = 0, k = n + 1;
        int wi;
        while (p <= k) {
            int sr = (p + k)/ 2;
            if (sprefi[sr] >= sprefi[wo - 1] + K) {
                wi = sr;
                k = sr - 1;
            } else {
                p = sr + 1;
            }
        }

        //cout << wj << " " << wo << " " << wi << "\n";

        if (wi != n + 1) {
            wyn = min(wyn, wi - i + 1 - K * 3);
        }
    }

    if (wyn == INT_MAX) {
        cout << -1 << "\n";
    } else {
        cout << wyn << "\n";
    }



    return 0;
}

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