oj.uz

Submission #369732

# Submission time Handle Problem Language Result Execution time Memory
369732 2021-02-22T10:15:00 Z Sorting Election (BOI18_election) C++17
0 / 100
 1 ms 492 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -