Submission #369821

#	Time	Username	Problem	Language	Result	Execution time	Memory
369821		Sorting	Election (BOI18_election)	C++17	100 / 100	570 ms	28096 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, ans;

        Node(){}
        Node(int x): prefix(max(x, 0)), suffix(max(x, 0)), ans(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);
            ret.ans = max(max(l.ans + r.sum, r.ans + l.sum), l.prefix + r.suffix);
            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 << ans.ans << "\n";
    }
}

Compilation message (stderr)

election.cpp: In constructor 'Segment_Tree::Node::Node(int)':
election.cpp:12:34: warning: 'Segment_Tree::Node::ans' will be initialized after [-Wreorder]
   12 |         int prefix, suffix, sum, ans;
      |                                  ^~~
election.cpp:12:29: warning:   'int Segment_Tree::Node::sum' [-Wreorder]
   12 |         int prefix, suffix, sum, ans;
      |                             ^~~
election.cpp:15:9: warning:   when initialized here [-Wreorder]
   15 |         Node(int x): prefix(max(x, 0)), suffix(max(x, 0)), ans(max(x, 0)), sum(x){}
      |         ^~~~

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