Submission #681353

#	Time	Username	Problem	Language	Result	Execution time	Memory
681353		finn__	Election (BOI18_election)	C++17	100 / 100	250 ms	28068 KiB

election

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int l, r, s, a;
};

inline node transition(node const &u, node const &v)
{
    return (node){
        .l = max(u.l, u.s + v.l),
        .r = max(v.r, v.s + u.r),
        .s = u.s + v.s,
        .a = max(u.l + v.r, max(u.a + v.s, v.a + u.s))};
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n;
    string s;
    cin >> n >> s;

    vector<node> tree(2 * (1 << (32 - __builtin_clz(n))), {0, 0, 0, 0});

    for (size_t i = 0; i < n; i++)
    {
        if (s[i] == 'C')
            tree[tree.size() / 2 + i] = {0, 0, -1, 0};
        else
            tree[tree.size() / 2 + i] = {1, 1, 1, 1};
    }

    for (size_t i = tree.size() / 2 - 1; i; i--)
        tree[i] = transition(tree[2 * i], tree[2 * i + 1]);

    size_t q;
    cin >> q;

    for (size_t z = 0; z < q; z++)
    {
        size_t i, j;
        cin >> i >> j;
        i += tree.size() / 2 - 1, j += tree.size() / 2 - 1;
        node x = {0, 0, 0, 0}, y = {0, 0, 0, 0};

        while (i <= j)
        {
            if (i & 1)
                x = transition(x, tree[i++]);
            if (!(j & 1))
                y = transition(tree[j--], y);

            i >>= 1;
            j >>= 1;
        }

        x = transition(x, y);
        cout << x.a << '\n';
    }
}

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18