Submission #1269737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269737		yanb	Election (BOI18_election)	C++20	100 / 100	1586 ms	76080 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using t3i = tuple<int, int, int>;

struct Node {
    int mn, mx, ans, s;

    Node() : mn(1e9), mx(-1e9), ans(0), s(0) {}

    Node(int mn, int mx, int ans, int s) : mn(mn), mx(mx), ans(ans), s(s) {}

    Node(int x) : mn(min(0ll, x)), mx(max(0ll, x)), ans(max(0ll, x)), s(x) {}

    Node operator+(const Node &o) const {
        return Node(min(mn, s + o.mn), max(mx, s + o.mx), max({ans, o.ans, s + o.mx - mn}), s + o.s);
    }
};

struct Tree {
    int n;
    vector<Node> st;

    Tree(int n, vector<int> &a) : n(n), st(4 * n) {
        _build(a, 1, 0, n - 1);
    }

    void _build(vector<int> &a, int v, int vl, int vr) {
        if (vl == vr) {
            st[v] = Node(a[vl]);
            return;
        }
        int vm = (vl + vr) / 2;
        _build(a, v * 2, vl, vm);
        _build(a, v * 2 + 1, vm + 1, vr);
        st[v] = st[v * 2] + st[v * 2 + 1];
    }

    Node _get(int l, int r, int v, int vl, int vr) {
        if (l <= vl && vr <= r) return st[v];
        if (r < vl || vr < l) return Node();
        int vm = (vl + vr) / 2;
        return _get(l, r, v * 2, vl, vm) + _get(l, r, v * 2 + 1, vm + 1, vr);
    }

    int get(int l, int r) {
        return _get(l, r, 1, 0, n - 1).ans;
    }
};

signed main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int q;
    cin >> q;

    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = (s[i] == 'C' ? 1 : -1);

    vector<int> pref(n + 1);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + a[i];
    }

    Tree st(n, a);

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        cout << st.get(l, r) - pref[r + 1] + pref[l] << "\n";
    }
}

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