Submission #1149400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149400		buzdi	Election (BOI18_election)	C++17	100 / 100	307 ms	21700 KiB

election

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int NMAX = 5e5;

struct TreeNode {
    int max_subarray_sum;
    int max_prefix_sum;
    int max_suffix_sum;
    int sum;

    TreeNode() {}
    TreeNode(int value) {
        max_subarray_sum = max_prefix_sum = max_suffix_sum = max(0, value);
        sum = value;
    }
};

struct Segment_Tree {
    TreeNode segtree[4 * NMAX + 1];
    
    TreeNode Combine(TreeNode left, TreeNode right) {
        TreeNode answer;
        answer.max_subarray_sum = max({left.max_subarray_sum, right.max_subarray_sum, left.max_suffix_sum + right.max_prefix_sum});
        answer.max_prefix_sum = max(left.max_prefix_sum, left.sum + right.max_prefix_sum);
        answer.max_suffix_sum = max(right.max_suffix_sum, right.sum + left.max_suffix_sum);
        answer.sum = left.sum + right.sum;
        return answer;
    }

    void Build(int node, int left, int right, int a[]) {
        if(left == right) {
            segtree[node] = TreeNode(a[left]);
            return;
        }

        int mid = (left + right) / 2;
        Build(node * 2, left, mid, a);
        Build(node * 2 + 1, mid + 1, right, a);
        segtree[node] = Combine(segtree[node * 2], segtree[node * 2 + 1]);
    }

    TreeNode Query(int node, int left, int right, int Qleft, int Qright) {
        if(left >= Qleft && right <= Qright) {
            return segtree[node];
        }

        int mid = (left + right) / 2;
        if(mid >= Qright) {
            return Query(node * 2, left, mid, Qleft, Qright);
        }
        if(mid + 1 <= Qleft) {
            return Query(node * 2 + 1, mid + 1, right, Qleft, Qright);
        }

        TreeNode left_node = Query(node * 2, left, mid, Qleft, Qright);
        TreeNode right_node = Query(node * 2 + 1, mid + 1, right, Qleft, Qright);
        return Combine(left_node, right_node);
    }
}segtree;

int n, q;
int a[NMAX + 1];

int Query(int left, int right) {
    TreeNode answer = segtree.Query(1, 1, n, left, right);
    return answer.max_subarray_sum - answer.sum;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        char s;
        cin >> s;
        a[i] = (s == 'C' ? 1 : -1);
    }

    cin >> q;
    segtree.Build(1, 1, n, a);
    while(q--) {
        int left, right;
        cin >> left >> right;
        cout << Query(left, right) << '\n';
    }

    return 0;
}

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