Submission #881753

#	Time	Username	Problem	Language	Result	Execution time	Memory
881753		AlphaMale06	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	10 ms	4832 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define pb push_back



signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int L, R;
    vector<int> posj, poso, posi;
    int pos[n];
    for(int i=0; i< n; i++){
        if(s[i]=='J'){
            posj.pb(i);
            pos[i]=posj.size()-1;
        }
        else if(s[i]=='O'){
            poso.pb(i);
            pos[i]=poso.size()-1;
        }
        else{
            posi.pb(i);
            pos[i]=posi.size()-1;
        }
    }
    int szj, szo, szi;
    szj=posj.size(); szo=poso.size(); szi=posi.size();
    int ans=1e9;
    for(int i=0; i+k<=szj; i++){
        int ind=posj[i+k-1];
        auto its=upper_bound(poso.begin(), poso.end(), ind);
        if(its==poso.end())break;
        int ind2=*its;
        ind2=pos[ind2];
        ind2+=k-1;
        if(ind2>=szo)break;
        its=upper_bound(posi.begin(), posi.end(), poso[ind2]);
        if(its==posi.end())break;
        int ind3=*its;
        ind3=pos[ind3];
        ind3+=k-1;
        if(ind3>=szi)break;
        ans=min(ans, posi[ind3]-posj[i]-3*k+1);
    }
    if(ans>1e8)cout << -1 << '\n';
    else cout << ans << '\n';
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:17:9: warning: unused variable 'L' [-Wunused-variable]
   17 |     int L, R;
      |         ^
ho_t2.cpp:17:12: warning: unused variable 'R' [-Wunused-variable]
   17 |     int L, R;
      |            ^

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