Submission #1100558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100558		vjudge1	Election (BOI18_election)	C++17	100 / 100	1324 ms	42780 KiB

election

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

const int MAXN = 5e5 + 10;

char c[MAXN];

struct Segment {
    
    struct Node {
        int pf, sf, sum, ans;
        Node()
        {
            pf = sf = sum = ans = 0;
        }
    } node[MAXN << 2];

    Node merge(Node l, Node r)
    {
        Node res;
        res.pf = max(l.pf, l.sum + r.pf);
        res.sf = max(r.sf, r.sum + l.sf);
        res.sum = l.sum + r.sum;
        res.ans = max(max(l.ans + r.sum, r.ans + l.sum), l.pf + r.sf);
        return res;
    }

    void initialize(int id, int l, int r)
    {
        if (l + 1 == r)
        {
            if (c[l] == 'T')
                node[id].pf = node[id].sf = node[id].sum = node[id].ans = 1;
            else
            {
                node[id].pf = node[id].sf = node[id].ans = 0;
                node[id].sum = -1;
            }
            return;
        }
        int mid = (l + r) >> 1;
        initialize(id << 1 | 0, l, mid);
        initialize(id << 1 | 1, mid, r);
        node[id] = merge(node[id << 1 | 0], node[id << 1 | 1]);
    }

    Node get(int id, int L, int R, int l, int r)
    {
        if (L == l && R == r)
        {
            return node[id];
        }
        int mid = (L + R) >> 1;
        Node res;
        if (l < mid)
            res = merge(res, get(id << 1 | 0, L, mid, l, min(r, mid)));
        if (r > mid)
            res = merge(res, get(id << 1 | 1, mid, R, max(l, mid), r));
        return res;
    }

} Seg;

int main()
{
    int n, q;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    Seg.initialize(1, 1, n + 1);
    cin >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        auto ans = Seg.get(1, 1, n + 1, l, r + 1);
        cout << ans.ans << endl;
    }
    return 0;
}

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