Submission #988811

#	Time	Username	Problem	Language	Result	Execution time	Memory
988811		IdanRosen	Election (BOI18_election)	C++98	0 / 100	16 ms	78680 KiB

election

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <ld, ld> pld;

struct seg_tree {
    struct node {
        int left = 0;
        int right = 0;

        int range_sz() { return right - left; }

        bool touches(int l, int r) { return left < r && l < right; }

        ll sum;
        ll min_prefix;
        ll min_suffix;
        ll local_ans;
    };

#define MAXN 500001
    node tree[4 * MAXN];

    template<typename T>
    void build(const vector <T> &arr) {
        build(arr, 1, 0, arr.size());
    }

    template<typename T>
    void build(const vector <T> &arr, int node, int curr_l, int curr_r) {
        if (curr_l == curr_r - 1) {
            tree[node].left = curr_l;
            tree[node].right = curr_r;

            tree[node].sum = arr[curr_l];
            tree[node].min_prefix = tree[node].min_suffix = min((ll) 0, arr[curr_l]);
            tree[node].local_ans = (arr[curr_l] == 1 ? 0 : 1);
            return;
        }

        int curr_m = curr_l + (curr_r - curr_l) / 2;

        build(arr, 2 * node, curr_l, curr_m);
        build(arr, 2 * node + 1, curr_m, curr_r);

        pull_index(node);
    }

    inline void pull_index(int node_in) {
        tree[node_in] = pull(tree[node_in * 2], tree[node_in * 2 + 1]);
    }

    node pull(node left, node right) {
        node ans;
        ans.left = left.left;
        ans.right = right.right;

        ans.sum = left.sum + right.sum;
        ans.min_prefix = min(left.min_prefix, left.sum + right.min_prefix);
        ans.min_suffix = min(right.min_suffix, left.min_suffix + right.sum);
        ans.local_ans = max(
                abs(left.min_prefix) + abs(right.min_suffix),
                max(
//                        abs(left.min_prefix) + max(0ll, abs(right.min_prefix) -
//                                                        (left.sum +
//                                                         abs(left.min_prefix))),
//                        abs(right.min_suffix) + max(0ll, abs(left.min_suffix) -
//                                                         (right.sum +
//                                                          abs(right.min_suffix)))
                        left.local_ans - right.sum,
                        -left.sum + right.local_ans
                )
        );

        return ans;
    }

    ll query(int query_l, int query_r) {
        return query(query_l, query_r, 1).local_ans;
    }

    node query(int query_l, int query_r, int node) {
        if (query_l <= tree[node].left && tree[node].right <= query_r) {
            return tree[node];
        }

        bool touches_left = tree[2 * node].touches(query_l, query_r);
        bool touches_right = tree[2 * node + 1].touches(query_l, query_r);

        if (!touches_right) return query(query_l, query_r, 2 * node);
        else if (!touches_left)return query(query_l, query_r, 2 * node + 1);
        else {
            return pull(
                    query(query_l, query_r, 2 * node),
                    query(query_l, query_r, 2 * node)
            );
        }
    }

};

seg_tree segtree;

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

    ll n;
    cin >> n;

    string str;
    cin >> str;

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

    segtree.build(arr);

    ll q;
    cin >> q;
    while (q--) {
        ll a, b;
        cin >> a >> b;
        a--;

        cout << segtree.query(a, b) << "\n";
    }

}

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