Submission #413572

#	Time	Username	Problem	Language	Result	Execution time	Memory
413572		Ozy	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	54 ms	11332 KiB

ho_t2

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl

#define pos first
#define id second
#define MAX 200000

lli n,k,a,res,J,O,I,o,i;
lli Jid[MAX+2],Oid[MAX+2],Iid[MAX+2],ini[MAX+2];
char arr[200002];
set< pair <lli,lli> > Os, Is;

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

    cin >> n >> k;
    rep(i,1,n) {
        cin >> arr[i];
        if (arr[i] == 'J') {
            J++;
            if (J >= k) Jid[J-k+1] = i;
            ini[J] = i;
        }
        else if (arr[i] == 'O') {
            O++;
            Os.insert({i,O});
            if (O >= k) Oid[O-k+1] = i;
        }
        else if (arr[i] == 'I') {
            I++;
            Is.insert({i,I});
            if (I >= k) Iid[I-k+1] = i;
        }
    }

    res = -1;
    rep(j,1,J) {
        if (Jid[j] == 0) break;

        if (Os.upper_bound({Jid[j],0}) == Os.end()) break;
        o = (*Os.upper_bound({Jid[j],0})).id;
        if (Oid[o] == 0) break;


        if (Is.upper_bound({Oid[o],0}) == Is.end()) break;
        i = (*Is.upper_bound({Oid[o],0})).id;
        if (Iid[i] == 0) break;

        a = (Iid[i]-ini[j]+1)-(k*3);
        if (a < res || res == -1) res = a;
    }

    cout << res;

    return 0;
}

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