Submission #1111345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111345		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	14 ms	4604 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pll pair<ll, ll>
ll n, k, pO[200001], pJ[200001], pI[200001], ans=1e18;
string str;
vector<ll> J, I;


int main(){
    cin >> n >> k;
    cin >> str;
    for(int i=1; i<=n; i++){
        if(str[i-1]=='J')
            J.push_back(i);
        if(str[i-1]=='I')
            I.push_back(i);
        if(str[i-1]=='O')pO[i]=pO[i-1]+1;
        else pO[i]=pO[i-1];
    }
    if(J.size()<k || I.size()<k || pO[n]<k){
        cout << -1 << endl;
        return 0;
    }
    for(int i=J.size()-1; i>=k-1; i--){
        int l=0, r=I.size()-1, mid, back=-1;
        while(l<=r){
            mid=(l+r)/2;
            if(pO[I[mid]]-pO[J[i]]<k){
                l=mid+1;
            }else{
                back=mid;
                r=mid-1;
            }
        }
        if(back==-1 || I.size() - back < k)continue;
        ans=min(ans, I[back+k-1]-J[i-k+1]+1-3*k);
    }
    if(ans==1e18)ans=-1;
    cout << ans << endl;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:23:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   23 |     if(J.size()<k || I.size()<k || pO[n]<k){
      |        ~~~~~~~~^~
ho_t2.cpp:23:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   23 |     if(J.size()<k || I.size()<k || pO[n]<k){
      |                      ~~~~~~~~^~
ho_t2.cpp:38:40: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |         if(back==-1 || I.size() - back < k)continue;
      |                        ~~~~~~~~~~~~~~~~^~~

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