Submission #860851

#	Time	Username	Problem	Language	Result	Execution time	Memory
860851		Blagoj	Election (BOI18_election)	C++17	100 / 100	444 ms	76332 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

struct Node {
    ll sum, pref, suff, ans;
};

int n, arr[(int) 5e5 + 10];

struct SegmentTree {
    vector<Node> sgt;

    SegmentTree(int n) {
        sgt.resize(4 * n);
    }

    Node merge(Node a, Node b) {
        return { a.sum + b.sum, max(a.pref, a.sum + b.pref), max(b.suff, a.suff + b.sum), max({0LL, a.pref + b.suff, a.sum + b.ans, a.ans + b.sum}) };
    }

    void build(int k = 1, int l = 0, int r = n - 1) {
        if (l == r) {
            sgt[k] = { arr[l], max(0, arr[l]), max(0, arr[l]), max(arr[l], 0) };
            return;
        }
        int m = (l + r) / 2;
        build(k * 2, l, m);
        build(k * 2 + 1, m + 1, r);
        sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
    }

    Node get(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return {0, 0, 0, 0};
        if (i <= l && r <= j) return sgt[k];
        int m = (l + r) / 2;
        return merge(get(k * 2, l, m, i, j), get(k * 2 + 1, m + 1, r, i, j));
    }

} sgt(5e5);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) arr[i] = (s[i] == 'C' ? -1 : 1);
    sgt.build();
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << sgt.get(1, 0, n - 1, --x, --y).ans << endl;
    }
}

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