Submission #1238231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238231		nasjes	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	12 ms	5848 KiB

ho_t2

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 5*1e6+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e18 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m;
pll a[dim];
ll op1[dim], pr[4][dim], pos[dim];
ll b[dim];
int main() {
    ll k, t, u0, v0;
    string s1;
    cin>>n>>k;
    cin>>s1;
    ll cnt1=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=3; j++)pr[j][i]=pr[j][i-1];
        if(s1[i-1]=='J')pr[1][i]++;
        else if(s1[i-1]=='I')pr[3][i]++;
        else{
            pr[2][i]++;
            cnt1++;
            pos[cnt1]=i;
          //  cout<<pos[cnt1]<<" ";
        }
    }

    //cout<<endl;
    ll ans=inf;
    for(int i=1; i<=n; i++){
        ll a1=0;
        ll a2=0;
        ll a3=0;
        if(s1[i-1]=='O'){
            ll cur=pr[2][i];
            if(cur+k-1>cnt1)continue;
            ll p2=pos[cur+k-1];
            ll p1=i;
            a2=(p2-p1+1-k);
            ll l=p2+1;
            ll r=n;

            while(r-l>=1){
                ll mid=(l+r)/2;
                if(pr[3][mid]-pr[3][p2]>=k){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }

            if(pr[3][l]-pr[3][p2]<k)continue;
            a3=(l-p2-k);
             l=0;
             r=p1-1;
            while(r-l>=1){
                ll mid=(l+r+1)/2;
                if(pr[1][p1]-pr[1][mid]<k){
                    r=mid-1;
                }
                else{
                    l=mid;
                }
            }
            if(pr[1][p1]-pr[1][l]<k)continue;
            a1=p1-l-1-k;
            ans=min(ans, a1+a2+a3);
        }
    }
    if(ans==inf)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

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