Submission #237625

# Submission time Handle Problem Language Result Execution time Memory
237625 2020-06-07T22:04:12 Z Sorting Election (BOI18_election) C++14
100 / 100
798 ms 54276 KB
#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.rbegin(), st.rend(), r) - st.rbegin());
        }
    }

    for(int i = 0; i < q; ++i)
        cout << answer[i] << "\n";
}
# Verdict Execution time Memory Grader output
1 Correct 21 ms 27776 KB Output is correct
2 Correct 21 ms 27776 KB Output is correct
3 Correct 22 ms 27776 KB Output is correct
4 Correct 24 ms 27904 KB Output is correct
5 Correct 21 ms 27776 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 21 ms 27776 KB Output is correct
2 Correct 21 ms 27776 KB Output is correct
3 Correct 22 ms 27776 KB Output is correct
4 Correct 24 ms 27904 KB Output is correct
5 Correct 21 ms 27776 KB Output is correct
6 Correct 89 ms 30456 KB Output is correct
7 Correct 76 ms 30584 KB Output is correct
8 Correct 88 ms 30712 KB Output is correct
9 Correct 84 ms 30968 KB Output is correct
10 Correct 102 ms 30968 KB Output is correct
11 Correct 96 ms 31308 KB Output is correct
12 Correct 91 ms 31224 KB Output is correct
13 Correct 97 ms 31352 KB Output is correct
14 Correct 87 ms 31224 KB Output is correct
15 Correct 88 ms 31096 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 21 ms 27776 KB Output is correct
2 Correct 21 ms 27776 KB Output is correct
3 Correct 22 ms 27776 KB Output is correct
4 Correct 24 ms 27904 KB Output is correct
5 Correct 21 ms 27776 KB Output is correct
6 Correct 89 ms 30456 KB Output is correct
7 Correct 76 ms 30584 KB Output is correct
8 Correct 88 ms 30712 KB Output is correct
9 Correct 84 ms 30968 KB Output is correct
10 Correct 102 ms 30968 KB Output is correct
11 Correct 96 ms 31308 KB Output is correct
12 Correct 91 ms 31224 KB Output is correct
13 Correct 97 ms 31352 KB Output is correct
14 Correct 87 ms 31224 KB Output is correct
15 Correct 88 ms 31096 KB Output is correct
16 Correct 783 ms 52376 KB Output is correct
17 Correct 511 ms 48548 KB Output is correct
18 Correct 600 ms 49544 KB Output is correct
19 Correct 614 ms 51256 KB Output is correct
20 Correct 722 ms 51724 KB Output is correct
21 Correct 798 ms 54108 KB Output is correct
22 Correct 685 ms 53424 KB Output is correct
23 Correct 797 ms 54276 KB Output is correct
24 Correct 702 ms 53560 KB Output is correct
25 Correct 684 ms 53004 KB Output is correct