Submission #1342766

#TimeUsernameProblemLanguageResultExecution timeMemory
1342766nagorn_phJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
9 ms3208 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));

const int mod = 1e9 + 7;
const int inf = 1e18;
const matrix II = {{1, 0}, {0, 1}};
const int N = 2e5 + 5;

void solve(){
    int n, k; cin >> n >> k;
    string s; cin >> s; s = ' ' + s;
    vector <int> j, o, i;
    for (int id = 1; id <= n; id++) {
        if (s[id] == 'J') j.emb(id);
        if (s[id] == 'O') o.emb(id);
        if (s[id] == 'I') i.emb(id);
    }
    int ans = inf;
    for (int id = 0; id + k - 1 < j.size(); id++) {
        int firstj = j[id];
        int lastj = j[id + k - 1];
        int firsto = lower_bound(all(o), lastj) - o.begin();
        if (firsto + k - 1 < o.size()) {
            int lasto = o[firsto + k - 1];
            int firsti = lower_bound(all(i), lasto) - i.begin();
            if (firsti + k - 1 < i.size()) {
                int lasti = i[firsti + k - 1];
                ans = min(ans, lasti - firstj + 1 - 3 * k);
            }
            else break;
        }
        else break;
    }
    cout << (ans == inf ? -1ll : ans);
}

int32_t main(){
    iShowSpeed;
    // int q; cin >> q; while (q--) 
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...