Submission #1045392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045392		shezitt	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	12 ms	5640 KiB

ho_t2

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

using namespace std;
using namespace __gnu_pbds;

using ll = long long;

#define int ll 
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define vi vector<int>
#define pb push_back
#define ii pair<int,int>
#define F first 
#define S second 
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define dbg(x) cerr << #x << ": " << x << endl
#define raya cerr << "========================" << endl

const int N = 2e5+5;

int n, k;
string s;

int contJ[N], contO[N], contI[N];

int findj(int i){
    int low = i, high = n-1;
    int j = -1;
    while(low <= high){
        int mid = low + (high - low) / 2;
        if(contJ[mid] - (i == 0 ? 0 : contJ[i-1]) >= k){
            j = mid;
            high = mid-1;
        } else {
            low = mid+1;
        }
    }
    return j;
}

int findl(int j){
    int low = j+1, high = n-1;
    int l = -1;

    while(low <= high){
        int mid = low + (high - low) / 2;
        if(contO[mid] - contO[j] >= k){
            l = mid;
            high = mid-1;
        } else {
            low = mid+1;
        }
    }

    return l;
}

int findm(int l){
    int low = l+1, high = n-1;
    int m = -1;
    while(low <= high){
        int mid = low + (high - low) / 2;
        if(contI[mid] - contI[l] >= k){
            m = mid;
            high = mid-1;
        } else {
            low = mid+1;
        }
    }
    return m;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    // contJ
    for(int i=0; i<n; ++i){

        contJ[i] += (s[i] == 'J');
        contO[i] += (s[i] == 'O');
        contI[i] += (s[i] == 'I');

        contJ[i+1] = contJ[i];
        contO[i+1] = contO[i];
        contI[i+1] = contI[i];
    }

    int ans = n;

    for(int i=0; i<n; ++i) if(s[i] == 'J'){
        // then go to j
        int j = findj(i);
        if(j == -1) continue;
        // then go to l
        int l = findl(j);
        if(l == -1) continue;
        // then go to m
        int m = findm(l);
        if(m == -1) continue;

        int cur = j - i + 1 - k;
        cur += l - j - k;
        cur += m - l - k;
        ans = min(ans, cur);

    }

    // assert(ans > -1);
    cout << (ans == n ? -1 : ans) << endl;

}

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