Submission #1217399

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

election

#include <iostream>
#include <vector>

using namespace std;

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

    Vote operator+(const Vote& other) const {
        Vote res;
        int tt = tr + other.tl;
        int cc = min(c, other.c);
        int match = min(tt, cc);
        res.tsum = tsum + other.tsum - match;
        res.c = c + other.c - 2 * match;
        if (res.c == 0) {
            res.tl = res.tr = tl + tt + other.tr - match;
        } else {
            res.tl = tl + (c < other.c ? tt - match : 0);
            res.tr = (c > other.c ? tt - match : 0) + other.tr;
        }

        // cout << "c: " << c << ", other.c: " << other.c << endl;
        // cout << "tl: " << tl << ", other.tl: " << other.tl << endl;
        // cout << "tr: " << tr << ", other.tr: " << other.tr << endl;
        // cout << "tt: " << tt << ", match: " << match << endl;
        // cout << "res.c: " << res.c << ", res.tl: " << res.tl << ", res.tr: " << res.tr << ", res.tsum: " << res.tsum << endl;
        // cout << "res: " << res.c << " " << res.tl << " " << res.tr << " " << res.tsum << endl;
        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 << res.tsum << endl;
    }
    return 0;
}

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