Submission #1298200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298200		aaa2312	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	0 ms	468 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;
const ll mod2 = 998244353;

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

ll pow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans *= a;
        b >>= 1;
        a *= a;
    }
    return ans;
}

ll pow(ll a, ll b, ll c) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % c;
        b >>= 1;
        a = (a * a) % c;
    }
    return ans;
}

void check(bool b) {
    if (b)
        cout << "Yes\n";
    else
        cout << "No\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
//    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        string s;
        cin >> s;
        ll q;
        cin >> q;
        vector<array<array<ll, 3>, 2>> tree(4 * n);
        function<array<array<ll, 3>, 2>(array<array<ll, 3>, 2>, array<array<ll, 3>, 2>)> merge = [&](
                const array<array<ll, 3>, 2> left, const array<array<ll, 3>, 2> right) -> array<array<ll, 3>, 2> {
            ll x = min(left[0][1], right[0][0]);
            ll x1 = min(left[1][1], right[1][0]);
            array<array<ll, 3>, 2> res{};
            res[0] = {left[0][0] + right[0][0] - x, left[0][1] + right[0][1] - x, left[0][2] + right[0][2] + x};
            res[1] = {left[1][0] + right[1][0] - x1, left[1][1] + right[1][1] - x1, left[1][2] + right[1][2] + x1};
            return res;
        };
        function<void(ll, ll, ll)> build = [&](ll v, ll l, ll r) {
            if (l == r) {
                tree[v][0] = {s[l] != 'C', s[l] == 'C', 0};
                tree[v][1] = {s[l] == 'C', s[l] != 'C', 0};
                return;
            }
            ll m = (l + r) / 2;
            build(2 * v, l, m);
            build(2 * v + 1, m + 1, r);
            tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
        };
        function<array<array<ll, 3>, 2>(ll, ll, ll, ll, ll)> query = [&](ll v, ll l, ll r, ll ql,
                                                                         ll qr) -> array<array<ll, 3>, 2> {
            if (ql > qr)return {array<ll, 3>{0, 0, 0}, array<ll, 3>{0, 0, 0}};
            if (ql == l && qr == r)return tree[v];
            ll m = (l + r) / 2;
            return merge(query(2 * v, l, m, ql, min(qr, m)), query(2 * v + 1, m + 1, r, max(ql, m + 1), qr));
        };
        build(1, 0, n - 1);
        vector<ll> pre(n + 1);
        set<ll> s1;
        for (int i = 0; i < n; ++i) {
            pre[i + 1] = pre[i] + (s[i] == 'C');
            if (s[i] == 'C')s1.insert(i);
        }
        while (q--) {
            ll l, r;
            cin >> l >> r;
            --l;
            --r;
            if (pre[r + 1] == pre[l])
                cout << r - l + 1 << '\n';
            else {
//                cout << pre[r + 1] - pre[l]<<'\n';
                cout << r - l + 1 - (pre[r + 1] - pre[l] + min(query(1, 0, n - 1, *s1.lower_bound(l) + 1, r)[1][2],
                                                               query(1, 0, n - 1, l, *--s1.upper_bound(r) - 1)[0][2]))
                     << '\n';
            }
        }
    }
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55