Submission #290603

#	Time	Username	Problem	Language	Result	Execution time	Memory
290603		achibasadzishvili	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	41 ms	5516 KiB

ho_t2

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,k,r[200005][3],ans;
string s;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k >> s;
    
    for(int i=0; i<s.size(); i++){
        if(i){
            r[i][0] = r[i - 1][0];
            r[i][1] = r[i - 1][1];
            r[i][2] = r[i - 1][2];
        }
        if(s[i] == 'J')r[i][0]++;
        if(s[i] == 'O')r[i][1]++;
        if(s[i] == 'I')r[i][2]++;
    }
    ll ans = -1;
    for(int i=0; i<s.size(); i++){
        ll mx = 0,st = i;
        for(int j=0; j<3; j++){
            ll l = st , R = (int)s.size() - 1, mid,ind=-1;
            ll val = 0;
            if(st)val = r[st - 1][j];
            while(R >= l){
                mid = (l + R) / 2;
                if(r[mid][j] - val >= k){
                    R = mid - 1;
                    ind = mid;
                }
                else {
                    l = mid + 1;
                }
            }
            if(ind == -1){
                mx = -1;
                break;
            }
            st = ind;
            mx = max(mx , ind);
        }
        if(mx == -1)continue;
        if(ans == -1)ans = n - 3 * k - i - (n - mx - 1);
        ans = min(ans , n - 3 * k - i - (n - mx - 1));
    }
    
    cout << ans << '\n';
    
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:13:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~
ho_t2.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~

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