Submission #861726

#	Time	Username	Problem	Language	Result	Execution time	Memory
861726		dbence	Election (BOI18_election)	C++14	100 / 100	483 ms	58100 KiB

election

#include <bits/stdc++.h>
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
using namespace std;
const int N = 5e5 + 1;
int n, q;

string t;

struct Data {
    int pre = 0, suf = 0, sum = 0, ans = 0;

    Data operator + (const Data &data) const {
        return {max(pre, sum + data.pre), max(data.suf, data.sum + suf), sum + data.sum, max(max(sum + data.ans, ans + data.sum), pre + data.suf)};
    }
};

struct Node {
    int l, r;
    Data data;
} node[N << 2];

void merge(int id, int l, int r) {
    node[id].data = node[l].data + node[r].data;
}

void build(int id, int l, int r) {
    node[id].l = l;
    node[id].r = r;
    if (l == r) {
        node[id].data.sum = (t[l - 1] == 'T') - (t[l - 1] == 'C');
        node[id].data.pre = max(0, node[id].data.sum);
        node[id].data.suf = max(0, node[id].data.sum);
        node[id].data.ans = max(0, node[id].data.sum);
        return;
    }
    int q = l + r >> 1;
    build(l(id), l, q);
    build(r(id), q + 1, r);
    merge(id, l(id), r(id));
}

Data query(int id, int l, int r) {
    if (node[id].l == l && node[id].r == r) {
        return node[id].data;
    }
    int q = node[id].l + node[id].r >> 1;
    Data res;

    if (l <= q) {
        res = res + query(l(id), l, min(q, r));
    }
    if (r > q) {
        res = res + query(r(id), max(q + 1, l), r);
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> t >> q;
    build(0, 1, n);

    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        
        Data res = query(0, l, r);
        cout << res.ans << "\n";
    }
}

Compilation message (stderr)

election.cpp: In function 'void build(int, int, int)':
election.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int q = l + r >> 1;
      |             ~~^~~
election.cpp: In function 'Data query(int, int, int)':
election.cpp:47:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int q = node[id].l + node[id].r >> 1;
      |             ~~~~~~~~~~~^~~~~~~~~~~~

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