oj.uz

Submission #802439

# Submission time Handle Problem Language Result Execution time Memory
802439 2023-08-02T12:15:56 Z borisAngelov Election (BOI18_election) C++17
100 / 100
 439 ms 42816 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 500005;

int n;
string s;

struct segment_tree
{
    struct state
    {
        int sum;
        int max_pref;
        int max_suff;
        int ans;

        state()
        {
            sum = 0;
            max_pref = 0;
            max_suff = 0;
            ans = 0;
        }

        state(int _sum, int _max_pref, int _max_suff, int _ans)
        {
            sum = _sum;
            max_pref = _max_pref;
            max_suff = _max_suff;
            ans = _ans;
        }
    };

    state tree[4 * maxn];

    state combine(state left_child, state right_child)
    {
        state result;

        result.sum = left_child.sum + right_child.sum;
        result.max_pref = max(left_child.max_pref, left_child.sum + right_child.max_pref);
        result.max_suff = max(right_child.max_suff, right_child.sum + left_child.max_suff);
        result.ans = max(max(left_child.ans + right_child.sum, left_child.sum + right_child.ans), left_child.max_pref + right_child.max_suff);

        return result;
    }

    void build(int node, int l, int r)
    {
        if (l == r)
        {
            if (s[l] == 'T')
            {
                tree[node] = state(1, 1, 1, 1);
            }
            else
            {
                tree[node] = state(-1, 0, 0, 0);
            }

            return;
        }

        int mid = (l + r) / 2;

        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);

        tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
    }

    state query(int node, int l, int r, int ql, int qr)
    {
        if (l > qr || r < ql)
        {
            return state(0, 0, 0, 0);
        }

        if (ql <= l && r <= qr)
        {
            return tree[node];
        }

        int mid = (l + r) / 2;

        return combine(query(2 * node, l, mid, ql, qr), query(2 * node + 1, mid + 1, r, ql, qr));
    }

    int query(int l, int r)
    {
        return query(1, 1, n, l, r).ans;
    }
};

segment_tree tree;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> s;
    s = '#' + s;

    tree.build(1, 1, n);

    int q;
    cin >> q;

    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << tree.query(l, r) << "\n";
    }

    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 19 ms 31648 KB Output is correct
3 Correct 18 ms 31668 KB Output is correct
4 Correct 18 ms 31664 KB Output is correct
5 Correct 20 ms 31624 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 19 ms 31648 KB Output is correct
3 Correct 18 ms 31668 KB Output is correct
4 Correct 18 ms 31664 KB Output is correct
5 Correct 20 ms 31624 KB Output is correct
6 Correct 59 ms 32972 KB Output is correct
7 Correct 48 ms 32884 KB Output is correct
8 Correct 64 ms 32840 KB Output is correct
9 Correct 59 ms 32848 KB Output is correct
10 Correct 60 ms 32832 KB Output is correct
11 Correct 59 ms 33024 KB Output is correct
12 Correct 61 ms 33064 KB Output is correct
13 Correct 72 ms 33116 KB Output is correct
14 Correct 77 ms 33032 KB Output is correct
15 Correct 70 ms 32988 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 19 ms 31648 KB Output is correct
3 Correct 18 ms 31668 KB Output is correct
4 Correct 18 ms 31664 KB Output is correct
5 Correct 20 ms 31624 KB Output is correct
6 Correct 59 ms 32972 KB Output is correct
7 Correct 48 ms 32884 KB Output is correct
8 Correct 64 ms 32840 KB Output is correct
9 Correct 59 ms 32848 KB Output is correct
10 Correct 60 ms 32832 KB Output is correct
11 Correct 59 ms 33024 KB Output is correct
12 Correct 61 ms 33064 KB Output is correct
13 Correct 72 ms 33116 KB Output is correct
14 Correct 77 ms 33032 KB Output is correct
15 Correct 70 ms 32988 KB Output is correct
16 Correct 424 ms 41876 KB Output is correct
17 Correct 345 ms 41372 KB Output is correct
18 Correct 375 ms 41672 KB Output is correct
19 Correct 313 ms 41168 KB Output is correct
20 Correct 417 ms 40976 KB Output is correct
21 Correct 439 ms 42720 KB Output is correct
22 Correct 393 ms 42660 KB Output is correct
23 Correct 425 ms 42816 KB Output is correct
24 Correct 395 ms 42480 KB Output is correct
25 Correct 424 ms 42020 KB Output is correct