Submission #1026915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026915		phoenix	Election (BOI18_election)	C++17	100 / 100	318 ms	28132 KiB

election

#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 19);

struct node {
    int s;
    int l;
    int r;
    int d;
} tr[2 * N];

node calc(node l, node r) {
    node res;
    res.s = l.s + r.s;
    res.l = max(l.l, l.s + r.l);
    res.r = max(r.r, r.s + l.r);
    res.d = max({l.s + r.d, l.d + r.s, l.l + r.r});
    return res;
}

int n;
string s;

void build(int l = 0, int r = N - 1, int v = 1) {
    if (l == r) {
        int c = (l > n || s[l] != 'C');
        tr[v].s = (c ? +1 : -1);
        tr[v].l = tr[v].r = tr[v].d;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, 2 * v);
    build(mid + 1, r, 2 * v + 1);
    tr[v] = calc(tr[2 * v], tr[2 * v + 1]);
}

node query(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr) 
        return node();
    if (ql <= l && r <= qr)
        return tr[v];
    int mid = (l + r) / 2;
    return calc(query(ql, qr, l, mid, 2 * v), query(ql, qr, mid + 1, r, 2 * v + 1));
}

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

    cin >> n;
    cin >> s;

    build();    

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        node t = query(l, r);
        cout << t.d << '\n';
    }
}

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