Submission #1211713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211713		dima2101	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	14 ms	8404 KiB

ho_t2

#include <bits/stdc++.h>

#define int long long

int give_sum(int l, int r, std::vector<int> &pref)
{
    if (l > r)
    {
        std::swap(l, r);
    }
    if (l == 0)
    {
        return pref[r];
    }
    return pref[r] - pref[l - 1];
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, k;
    std::cin >> n >> k;

    std::string s;
    std::cin >> s;

    std::vector<int> prev_j(n);
    std::vector<int> next_i(n);
    std::vector<int> pref_j(n);
    std::vector<int> pref_i(n);
    std::vector<int> pref_o(n);
    pref_j[0] = (s[0] == 'J');
    pref_i[0] = (s[0] == 'I');
    pref_o[0] = (s[0] == 'O');
    int last_j = -1;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'J')
        {
            last_j = i;
        }
        prev_j[i] = last_j;
        if (i != 0)
        {
            pref_j[i] = pref_j[i - 1] + (s[i] == 'J');
            pref_i[i] = pref_i[i - 1] + (s[i] == 'I');
            pref_o[i] = pref_o[i - 1] + (s[i] == 'O');
        }
    }

    int last_i = -1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (s[i] == 'I')
        {
            last_i = i;
        }
        next_i[i] = last_i;
    }
    int ans = 1e9;
    for (int i = 0; i < n; i++)
    {
        if (s[i] != 'O')
            continue;

        int l = i - 1, r = n;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;

            if (give_sum(i, mid, pref_o) < k)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }

        if (r == n)
        {
            continue;
        }

        int start = i;
        int stop = r;
        int now = (stop - start + 1) - k;

        l = -1, r = start + 1;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (give_sum(mid, start, pref_j) < k)
            {
                r = mid;
            }
            else
            {
                l = mid;
            }
        }

        if (l == -1)
        {
            continue;
        }
        // std::cout << now << std::endl;
        now += (std::abs(start - l)) - k;

        l = stop - 1,
        r = n;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (give_sum(stop, mid, pref_i) < k)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }
        if (r == n)
        {
            continue;
        }
        // std::cout << now << ' ' << r << ' ' << tmp << std::endl;
        now += (r - stop) - k;
        // std::cout << now << std::endl;
        ans = std::min(ans, now);
    }
    if (ans == 1e9)
    {
        std::cout << -1;
        return 0;
    }
    std::cout << ans;
}

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