Submission #253259

#	Time	Username	Problem	Language	Result	Execution time	Memory
253259		doowey	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	14 ms	1816 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;
vector<int> lis[3];

int main(){
    fastIO;
    int n, k;
    cin >> n >> k;
    char f;
    int x;
    for(int i = 1; i <= n; i ++ ){
        cin >> f;
        if(f == 'J')
            x = 0;
        else if(f == 'O')
            x = 1;
        else
            x = 2;
        lis[x].push_back(i);
    }
    int nx;
    int pp;
    int shi;
    int fq;
    int en;
    int idx;
    int ans = (int)1e9;
    for(int i = 0 ; i < lis[0].size(); i ++ ){
        if(i + k - 1 < lis[0].size()){
            nx = lis[0][i + k - 1];
            pp = upper_bound(lis[1].begin(), lis[1].end(), nx) - lis[1].begin();
            if(pp + k - 1 < lis[1].size()){
                shi = lis[1][pp + k - 1];
                fq = upper_bound(lis[2].begin(), lis[2].end(), shi) - lis[2].begin();
                if(fq + k - 1 < lis[2].size()){
                    en = lis[2][fq + k - 1];
                    idx = en - lis[0][i] + 1;
                    ans = min(ans, idx-3*k);
                }
            }
        }
    }
    if(ans == (int)1e9)
        cout << -1 << "\n";
    else
        cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < lis[0].size(); i ++ ){
                     ~~^~~~~~~~~~~~~~~
ho_t2.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i + k - 1 < lis[0].size()){
            ~~~~~~~~~~^~~~~~~~~~~~~~~
ho_t2.cpp:43:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(pp + k - 1 < lis[1].size()){
                ~~~~~~~~~~~^~~~~~~~~~~~~~~
ho_t2.cpp:46:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(fq + k - 1 < lis[2].size()){
                    ~~~~~~~~~~~^~~~~~~~~~~~~~~

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