Submission #1021076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021076		phoenix	Election (BOI18_election)	C++17	0 / 100	13 ms	12632 KiB

election

#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 19);

struct node {
    int pre;
    int mid;
    int suf;
} tr[2 * N];

node calc(node l, node r) {
    if (!l.mid) {
        r.pre += l.pre;
        if (!r.mid) r.suf += l.suf;
        return r;  
    }
    if (!r.mid) {
        l.suf += r.suf;
        return l;  
    }
    int A = l.mid;
    int B = l.suf + r.pre;
    int C = r.mid;
    int k = min({A, B, C});
    A -= k, B -= k, C -= k;

    node res;
    res.pre = l.pre + (!A) * B + (!A && !C) * r.suf;
    res.mid = A + C;
    res.suf = r.suf + (!C) * B + (!C && !A) * l.pre;
    return res;
}

int n;
string s;

void build(int l = 0, int r = N - 1, int v = 1) {
    if (l == r) {
        bool c = (l > n || s[l] != 'C');
        tr[v].pre = c;
        tr[v].suf = c;
        tr[v].mid = !c;
        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;

    s  = '#' + s;
    build();
    

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        node t = query(l, r);
        cout << t.pre + (t.mid > 0) * t.suf << '\n';
    }
}

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