Submission #1240286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240286		chikien2009	Election (BOI18_election)	C++20	100 / 100	350 ms	20400 KiB

election

#include <bits/stdc++.h>

using namespace std;

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

int n, q, x, y;
string s;

struct NODE
{
    int a, b, c, d;

    inline NODE operator*(NODE inp)
    {
        NODE res;
        res.a = max(this->a, this->c + inp.a);
        res.b = max(this->b + inp.c, inp.b);
        res.c = this->c + inp.c;
        res.d = max({this->a + inp.b, this->d + inp.c, this->c + inp.d});\
        return res;
    }
};

struct SEGMENT_TREE
{
    NODE tree[2000000];
    inline void Build(int ind, int l, int r)
    {
        if (l == r)
        {
            tree[ind].a = tree[ind].b = tree[ind].d = (s[l] == 'T' ? 1 : 0);
            tree[ind].c = (s[l] == 'T' ? 1 : -1);
            return;
        }
        int m = (l + r) >> 1;
        Build(ind << 1, l, m);
        Build(ind << 1 | 1, m + 1, r);
        tree[ind] = tree[ind << 1] * tree[ind << 1 | 1];
    }
    inline NODE Get(int ind, int l, int r, int x, int y)
    {
        if (r < x || y < l)
        {
            return NODE();
        }
        if (x <= l && r <= y)
        {
            return tree[ind];
        }
        int m = (l + r) >> 1;
        return Get(ind << 1, l, m, x, y) * Get(ind << 1 | 1, m + 1, r, x, y);
    }
} st;

int main()
{
    setup();

    cin >> n >> s >> q;
    s = '#' + s;
    st.Build(1, 1, n);
    while (q--)
    {
        cin >> x >> y;
        cout << st.Get(1, 1, n, x, y).d << "\n";
    }
    return 0;
}

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