Submission #1217351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217351		stevend57	Election (BOI18_election)	C++20	0 / 100	2 ms	320 KiB

election

#include <iostream>
#include <vector>

using namespace std;

struct Vote {
    int cl, cr, tl, tr;
    Vote(char c = ' ') {
        cl = cr = tl = tr = 0;
        if (c == 'C') {
            cl = cr = 1;
        } else if (c == 'T') {
            tl = tr = 1;
        }
    }

    Vote operator+(const Vote& other) const {
        Vote res;
        int matchl = min(cl, other.tl);
        int matchr = min(other.cr, tr);
        res.cl = cl + other.cl - matchl;
        res.tl = tl + other.tl - matchl;
        res.cr = other.cr + cr - matchr;
        res.tr = other.tr + tr - matchr;
        return res;
    }
};

struct St {
    int n;
    vector<Vote> t; 
    St(int n) : n(n), t(n << 1) {}

    void build(const string& s) {
        for (size_t i = 0; i < s.size(); ++i) {
            t[n + i] = Vote(s[i]);
        }
        for (int i = n - 1; i > 0; --i) {
            t[i] = t[i << 1] + t[i << 1 | 1];
        }
    }

    Vote query(int l, int r) {
        Vote resl, resr;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resl = resl + t[l++];
            if (r & 1) resr = t[--r] + resr;
        }
        return resl + resr;
    }
};

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    St st(n);
    st.build(s);
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        Vote res = st.query(l - 1, r);
        cout << max(res.tl, res.tr) << endl;
    }
    return 0;
}

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