Submission #861661

#	Time	Username	Problem	Language	Result	Execution time	Memory
861661		iskhakkutbilim	Election (BOI18_election)	C++17	100 / 100	442 ms	76488 KiB

election

#include <bits/stdc++.h>
 
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define ll long long
 
struct Node{
    ll sum, pref, suff, ans;
};
 
int n, arr[(int)5e5 + 10];
 
struct SegmentTree{
    vector<Node> sgt;
    SegmentTree(int n){
        sgt.resize(4 * n);
    }
    Node merge(Node a, Node b){
        return { a.sum + b.sum, max(a.pref, a.sum + b.pref), max(b.suff, a.suff + b.sum), 
		max({0LL, a.pref + b.suff, a.sum + b.ans, a.ans + b.sum}) };
    }
    void build(int k = 1, int l = 0, int r = n - 1){
        if(l == r){
            sgt[k] = { arr[l], max(0, arr[l]), max(0, arr[l]), max(arr[l], 0) };
            return;
        }
        int m = (l + r) / 2;
        build(k * 2, l, m);
        build(k * 2 + 1, m + 1, r);
        sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
    }
    Node get(int k, int l, int r, int i, int j){
        if (l > j || r < i) return {0, 0, 0, 0};
        if (i <= l && r <= j) return sgt[k];
        int m = (l + r) / 2;
        return merge(get(k * 2, l, m, i, j), get(k * 2 + 1, m + 1, r, i, j));
    }
 
} sgt(5e5);
 
main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) arr[i] = (s[i] == 'C' ? -1 : 1);
    sgt.build();
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << sgt.get(1, 0, n - 1, --x, --y).ans << '\n';
    }
}

Compilation message (stderr)

election.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main() {
      | ^~~~

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