Submission #237624

#	Time	Username	Problem	Language	Result	Execution time	Memory
237624		Sorting	Election (BOI18_election)	C++14	0 / 100	21 ms	27776 KiB

election

#include <bits/stdc++.h>

using namespace std;

template<size_t t_N>
struct Segment_Tree{
    struct Node{
        int min_suffix, sum;

        Node(){
            min_suffix = 0;
            sum = 0;
        }

        Node(int min_suffix, int sum){
            this->min_suffix = min_suffix;
            this->sum = sum;
        }

        friend Node merge(const Node &l, const Node &r){
            Node answer;
            answer.sum = l.sum + r.sum;
            answer.min_suffix = min(r.min_suffix, l.min_suffix + r.sum);
            return answer;
        }
    };

    Node nodes[4 * t_N];

    void update(int index, int l, int r, int s, int value){
        if(s < l || r < s)
            return;
        if(l == r){
            nodes[index] = {min(value, 0), value};
            return;
        }

        int mid = (l + r) >> 1;
        update(2 * index + 1, l, mid, s, value);
        update(2 * index + 2, mid + 1, r, s, value);

        nodes[index] = merge(nodes[2 * index + 1], nodes[2 * index + 2]);
    }

    Node query_node(int index, int l, int r, int sl, int sr){
        if(sl > r || sr < l)
            return {0, 0};
        if(sl <= l && r <= sr)
            return nodes[index];

        int mid = (l + r) >> 1;
        Node lvalue = query_node(2 * index + 1, l, mid, sl, sr);
        Node rvalue = query_node(2 * index + 2, mid + 1, r, sl, sr);

        return merge(lvalue, rvalue);
    }

    int query(int index, int l, int r, int sl, int sr){
        return query_node(index, l, r, sl, sr).min_suffix;
    }
};

const int mx_N = 5e5 + 3;

int n, q;
string s;

int a[mx_N];
vector<pair<int, int>> queries[mx_N];
Segment_Tree<mx_N> segment_tree;

int answer[mx_N];

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

    cin >> n >> s;

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

    cin >> q;
    for(int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r;

        queries[l].push_back({r, i});
    }

    for(int i = 1; i <= n; ++i)
        segment_tree.update(0, 1, n, i, a[i]);

    vector<int> st;
    for(int i = n; i >= 1; --i){
        if(a[i] == 1){
            if(!st.empty()){
                segment_tree.update(0, 1, n, st.back(), -1);
                st.pop_back();
            }
        }
        else{
            segment_tree.update(0, 1, n, i, 0);
            st.push_back(i);
        }

        for(auto pp: queries[i]){
            int r = pp.first;
            int index = pp.second;
            answer[index] = -segment_tree.query(0, 1, n, i, r) + (upper_bound(st.begin(), st.end(), r) - st.begin());
        }
    }

    for(int i = 0; i < q; ++i)
        cout << answer[i] << "\n";
}

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