Submission #1266106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266106		trinm01	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	8 ms	5452 KiB

ho_t2

// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const ll oo = 1e18+7;  
const int base = 0;

int n, k;
string s;

int nxt1[MAXN], nxt2[MAXN], nxt3[MAXN];

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

    // freopen("test.txt", "r", stdin);
    // freopen("o2.out", "w", stdout); 

    // if(fopen(".inp", "r")){
    //     freopen(".inp", "r", stdin);
    //     freopen(".out", "w", stdout);
    // }   

    cin >> n >> k;
    cin >> s;
    s="."+s;
    s=s+".";

    int dm, j;
    dm=0, j=n+1;
    FOD(i, n, 1){
        if(s[i]=='J'){
            dm++;
        }
        if(dm>=k){
            while(dm>=k){
                if(s[j]=='J'){
                    dm--;
                }
                j--;
            }
            if(s[j+1]=='J'){
                j++;
                dm++;
            }
        }
        if(dm==k){
            nxt1[i]=j;
        }
    }
    dm=0, j=n+1;
    FOD(i, n, 1){
        if(s[i]=='O'){
            dm++;
        }
        if(dm>=k){
            while(dm>=k){
                if(s[j]=='O'){
                    dm--;
                }
                j--;
            }
            if(s[j+1]=='O'){
                j++;
                dm++;
            }
        }
        if(dm==k){
            nxt2[i]=j;
        }
    }
    dm=0, j=n+1;
    FOD(i, n, 1){
        if(s[i]=='I'){
            dm++;
        }
        if(dm>=k){
            while(dm>=k){
                if(s[j]=='I'){
                    dm--;
                }
                j--;
            }
            if(s[j+1]=='I'){
                j++;
                dm++;
            }
        }
        if(dm==k){
            nxt3[i]=j;
        }
    }
    
    int ans=oo;
    FOR(i, 1, n){
        int a=nxt1[i];
        if(a==0) break;
        a=nxt2[a+1];
        if(a==0) break;
        a=nxt3[a+1];
        if(a==0) break;
        ans=min(ans, a-i+1-k*3);
    }

    if(ans==oo) ans=-1;
    cout << ans;
    
    return 0;
}

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