Submission #1311584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311584		dm2010	Election (BOI18_election)	C++20	0 / 100	1 ms	332 KiB

election

#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    int n;
    vector<int> tmin, tmax;

    SegTree(const vector<int>& a) {
        n = a.size();
        tmin.resize(4 * n);
        tmax.resize(4 * n);
        build(1, 0, n - 1, a);
    }

    void build(int v, int l, int r, const vector<int>& a) {
        if (l == r) {
            tmin[v] = tmax[v] = a[l];
        } else {
            int m = (l + r) / 2;
            build(v * 2, l, m, a);
            build(v * 2 + 1, m + 1, r, a);
            tmin[v] = min(tmin[v * 2], tmin[v * 2 + 1]);
            tmax[v] = max(tmax[v * 2], tmax[v * 2 + 1]);
        }
    }

    int queryMin(int v, int l, int r, int ql, int qr) {
        if (qr < l || ql > r) return INT_MAX;
        if (ql <= l && r <= qr) return tmin[v];
        int m = (l + r) / 2;
        return min(queryMin(v * 2, l, m, ql, qr),
                   queryMin(v * 2 + 1, m + 1, r, ql, qr));
    }

    int queryMax(int v, int l, int r, int ql, int qr) {
        if (qr < l || ql > r) return INT_MIN;
        if (ql <= l && r <= qr) return tmax[v];
        int m = (l + r) / 2;
        return max(queryMax(v * 2, l, m, ql, qr),
                   queryMax(v * 2 + 1, m + 1, r, ql, qr));
    }

    int getMin(int l, int r) { return queryMin(1, 0, n - 1, l, r); }
    int getMax(int l, int r) { return queryMax(1, 0, n - 1, l, r); }
};

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

    int N;
    cin >> N;

    string S;
    cin >> S;

    vector<int> pref(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        pref[i] = pref[i - 1] + (S[i - 1] == 'C' ? 1 : -1);
    }

    SegTree st(pref);

    int Q;
    cin >> Q;

    while (Q--) {
        int L, R;
        cin >> L >> R;

        int minPref = st.getMin(L, R);
        int forward = max(0, pref[L - 1] - minPref);

        int maxPref = st.getMax(L - 1, R - 1);
        int backward = max(0, maxPref - pref[R]);

        cout << max(forward, backward) << "\n";
    }

    return 0;
}

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