Submission #253742

#	Time	Username	Problem	Language	Result	Execution time	Memory
253742		Sorting	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	45 ms	5668 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

const int k_N = 2e5 + 3;

int n, k;
string s, joi = "JOI";

int nxt[k_N][3];
int cnt[k_N][3];

int sum(int l, int r, int idx){
    if(l == 0) return cnt[r][idx];
    return cnt[r][idx] - cnt[l - 1][idx];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    cin >> s;

    for(int j = 0; j < 3; ++j)
        cnt[0][j] = (s[0] == joi[j]);

    for(int i = 1; i < s.size(); ++i)
        for(int j = 0; j < 3; ++j)
            cnt[i][j] = (s[i] == joi[j]) + cnt[i - 1][j];

    for(int i = 0; i < n; ++i){
        for(int idx = 0; idx < 3; ++idx){

            int l = i, r = n;
            while(l != r){
                int mid = (l + r) >> 1;
                if(sum(i, mid, idx) >= k)
                    r = mid;
                else
                    l = mid + 1;
            }

            nxt[i][idx] = l;
        }
        //cout << "nxt[" << i << "] = " << l << "\n";
    }
    nxt[n][0] = nxt[n][1] = nxt[n][2] = n;

    int ans = n + 1;
    for(int i = 0; i < n; ++i){
        if(s[i] != 'J') continue;

        int curr = i;
        if(nxt[curr][0] != n){
            curr = nxt[curr][0] + 1;
            if(nxt[curr][1] != n){
                curr = nxt[curr][1] + 1;
                if(nxt[curr][2] != n){
                    int en = nxt[curr][2];
                    ans = min(ans, en - i + 1 - 3 * k);
                }
            }
        }
    }

    if(ans == n + 1) ans = -1;
    cout << ans << "\n";
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < s.size(); ++i)
                    ~~^~~~~~~~~~

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