oj.uz

Submission #1045392

# Submission time Handle Problem Language Result Execution time Memory
1045392 2024-08-05T22:47:18 Z shezitt JJOOII 2 (JOI20_ho_t2) C++14
100 / 100
 12 ms 5640 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;

#define int ll 
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define vi vector<int>
#define pb push_back
#define ii pair<int,int>
#define F first 
#define S second 
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define dbg(x) cerr << #x << ": " << x << endl
#define raya cerr << "========================" << endl

const int N = 2e5+5;

int n, k;
string s;

int contJ[N], contO[N], contI[N];

int findj(int i){
    int low = i, high = n-1;
    int j = -1;
    while(low <= high){
        int mid = low + (high - low) / 2;
        if(contJ[mid] - (i == 0 ? 0 : contJ[i-1]) >= k){
            j = mid;
            high = mid-1;
        } else {
            low = mid+1;
        }
    }
    return j;
}

int findl(int j){
    int low = j+1, high = n-1;
    int l = -1;

    while(low <= high){
        int mid = low + (high - low) / 2;
        if(contO[mid] - contO[j] >= k){
            l = mid;
            high = mid-1;
        } else {
            low = mid+1;
        }
    }

    return l;
}

int findm(int l){
    int low = l+1, high = n-1;
    int m = -1;
    while(low <= high){
        int mid = low + (high - low) / 2;
        if(contI[mid] - contI[l] >= k){
            m = mid;
            high = mid-1;
        } else {
            low = mid+1;
        }
    }
    return m;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    cin >> s;

    // contJ
    for(int i=0; i<n; ++i){

        contJ[i] += (s[i] == 'J');
        contO[i] += (s[i] == 'O');
        contI[i] += (s[i] == 'I');

        contJ[i+1] = contJ[i];
        contO[i+1] = contO[i];
        contI[i+1] = contI[i];
    }

    int ans = n;

    for(int i=0; i<n; ++i) if(s[i] == 'J'){
        // then go to j
        int j = findj(i);
        if(j == -1) continue;
        // then go to l
        int l = findl(j);
        if(l == -1) continue;
        // then go to m
        int m = findm(l);
        if(m == -1) continue;

        int cur = j - i + 1 - k;
        cur += l - j - k;
        cur += m - l - k;
        ans = min(ans, cur);

    }

    // assert(ans > -1);
    cout << (ans == n ? -1 : ans) << endl;

}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct

Subtask #3
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 7 ms 5096 KB Output is correct
37 Correct 7 ms 5352 KB Output is correct
38 Correct 8 ms 5352 KB Output is correct
39 Correct 11 ms 5352 KB Output is correct
40 Correct 7 ms 5352 KB Output is correct
41 Correct 9 ms 5608 KB Output is correct
42 Correct 12 ms 5604 KB Output is correct
43 Correct 4 ms 3676 KB Output is correct
44 Correct 5 ms 4328 KB Output is correct
45 Correct 6 ms 5608 KB Output is correct
46 Correct 6 ms 5608 KB Output is correct
47 Correct 6 ms 5608 KB Output is correct
48 Correct 7 ms 5636 KB Output is correct
49 Correct 4 ms 3816 KB Output is correct
50 Correct 6 ms 5512 KB Output is correct
51 Correct 6 ms 5604 KB Output is correct
52 Correct 4 ms 5352 KB Output is correct
53 Correct 4 ms 5640 KB Output is correct
54 Correct 9 ms 5604 KB Output is correct
55 Correct 5 ms 5608 KB Output is correct
56 Correct 5 ms 5608 KB Output is correct