Submission #1011787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011787		gyg	Election (BOI18_election)	C++17	100 / 100	1159 ms	33976 KiB

election

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 5;

int n;
array<bool, MAX_N> a;

struct Node {
    int l_open, l_close;
    int r_open, r_close;
    int pairs;
} st[4 * MAX_N];
Node merge(Node x, Node y) {
    int l_del = min(x.l_open, y.l_close);
    x.l_open -= l_del, y.l_close -= l_del;
    int r_del = min(x.r_open, y.r_close);
    x.r_open -= r_del, y.r_close -= r_del;

    x.pairs = min(x.pairs, x.r_open);
    y.pairs = min(y.pairs, y.l_close);

    Node ans = {x.l_open + y.l_open, x.l_close + y.l_close, 
                x.r_open + y.r_open, x.r_close + y.r_close,
                x.pairs + y.pairs};
    if (x.r_open > x.pairs && y.l_close > y.pairs)
        ans.pairs += min(x.r_open - x.pairs, y.l_close - y.pairs);
    return ans;
}
void build(int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        if (a[lo] == 1) st[u].l_open++, st[u].r_close++;
        else st[u].l_close++, st[u].r_open++, st[u].pairs++;
        return;
    }
    int mid = (lo + hi) / 2;
    build(2 * u, lo, mid), build(2 * u + 1, mid + 1, hi);
    st[u] = merge(st[2 * u], st[2 * u + 1]);
}
Node query(int l, int r, int u = 1, int lo = 1, int hi = n) {
    if (r < lo || hi < l) return Node();
    if (l <= lo && hi <= r) return st[u];
    int mid = (lo + hi) / 2;
    return merge(query(l, r, 2 * u, lo, mid), query(l, r, 2 * u + 1, mid + 1, hi));
}

int main() {
    // freopen("elec.in", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char ch; cin >> ch;
        a[i] = (ch == 'C');
    }

    build();

    int q; cin >> q;
    for (int i = 1; i <= q; i++) {
        int l, r; cin >> l >> r;
        Node resp = query(l, r);
        int ans = resp.l_close + resp.r_open - resp.pairs;
        cout << ans << '\n';
    }
}

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