Submission #997639

#	Time	Username	Problem	Language	Result	Execution time	Memory
997639		mariamp1	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	14 ms	5676 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
const int N = 2e5 + 5, mod = 1e9+7;
vector<pair<int, int> > vec;
multiset<int> st;
int minn = 1e9;
int last[N];
int n; 
int pref[3][N], k;
int findd(int ind, int type){
    int l = ind; int r = n; int anss = -1;
    while(l <= r){
        int mid = l + (r-l)/2;
        if( pref[type][mid] - pref[type][ind - 1] >= k){
            anss = mid;
            r = mid - 1;
        }else l = mid + 1;
    }
    return anss;
}
int32_t main(){
	cin >> n >> k;
    string s; cin >> s;
    s = "*" + s;
    for(int i = 1; i <= n; i++){
        pref[0][i] = pref[0][i - 1] + (s[i] == 'J');
        pref[1][i] = pref[1][i - 1] + (s[i] == 'O');
        pref[2][i] = pref[2][i - 1] + (s[i] == 'I');
    }
    for(int i = 1; i <= n; i++){
        if(s[i] != 'J') continue;
        int mekJ = findd(i, 0);
        if (mekJ == -1) break;
        int mekO = findd(mekJ, 1);
        if (mekO == -1) break;
        int mekI = findd(mekO, 2);
        if (mekI == -1) break;
        int l = i;
        int r = mekI;
        minn = min(minn, r - l + 1 - 3 * k);
    }
    if(minn == 1e9) cout << -1 << endl;
    else 
        cout << minn << endl;
}

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