Submission #369732

#	Time	Username	Problem	Language	Result	Execution time	Memory
369732		Sorting	Election (BOI18_election)	C++17	0 / 100	1 ms	492 KiB

election

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 3;

int n, q;
string s;

struct Segment_Tree{
    struct Node{
        int prefix, suffix, sum;

        Node(){}
        Node(int x): prefix(max(x, 0)), suffix(max(x, 0)), sum(x){}

        friend Node merge(Node l, Node r){
            Node ret;
            ret.sum = l.sum + r.sum;
            ret.prefix = max(l.prefix, r.prefix + l.sum);
            ret.suffix = max(r.suffix, l.suffix + r.sum);
            return ret;
        }
    };

    Node nd[4 * N];

    void init(int i = 0, int l = 0, int r = n - 1){
        if(l == r){
            nd[i] = Node((s[l] == 'C') ? -1 : 1);
            return;
        }

        int mid = (l + r) >> 1;
        init(2 * i + 1, l, mid);
        init(2 * i + 2, mid + 1, r);
        nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
    }

    Node query(int l2, int r2, int i = 0, int l = 0, int r = n - 1){
        if(l2 <= l && r <= r2) return nd[i];

        int mid = (l + r) >> 1;
        if(mid >= l2){
            if(mid + 1 <= r2)
                return merge(query(l2, r2, 2 * i + 1, l, mid), query(l2, r2, 2 * i + 2, mid + 1, r));
            return query(l2, r2, 2 * i + 1, l, mid);
        }
        return query(l2, r2, 2 * i + 2, mid + 1, r);
    }
} st;

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

    cin >> n >> s;
    st.init();
    cin >> q;
    for(int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r;
        --l, --r;
        Segment_Tree::Node ans = st.query(l, r);
        cout << max(ans.prefix, ans.suffix) << "\n";
    }
}

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