Submission #1264740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264740		giaminh2211	Election (BOI18_election)	C++20	100 / 100	359 ms	21592 KiB

election

#include <bits/stdc++.h>

using namespace std;
using ll=long long;
const int N=5e5+13;
int n, q;
int a[N];

struct Node {
    int pre, suf, sum, res;

    Node operator+(const Node& other) const {
        return {
            max(pre, sum + other.pre),
            max(other.suf, other.sum + suf),
            sum + other.sum,
            max({res + other.sum, sum + other.res, pre + other.suf})
        };
    }
};

Node st[N * 4];

void build(int id, int l, int r) {
    if (l == r) {
        st[id] = {
            max(0, a[l]),
            max(0, a[l]),
            a[l],
            (a[l] == 1 ? 1 : 0)
        };
        return;
    }

    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

Node query(int id, int l, int r, int u, int v) {
    if (r < u || l > v) return {0, 0, 0, 0};
    if (u <= l && r <= v) return st[id];

    int mid = (l + r) / 2;
    return query(id * 2, l, mid, u, v) + query(id * 2 + 1, mid + 1, r, u, v);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        a[i] = (c == 'T' ? 1 : -1);
    }

    build(1, 1, n);

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

    return 0;
}

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