Submission #1154129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154129		byunjaewoo	Election (BOI18_election)	C++20	100 / 100	316 ms	36692 KiB

election

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=500010;
int n, q;
string t;

class seg {
public:
    void init() {init(1, 1, n);}
    int query(int l, int r) {return query(1, 1, n, l, r).v;}
private:
    struct Data {int l, r, s, v;};
    Data tree[4*N];
    Data Merge(Data a, Data b) {
        Data ret;
        ret.l=max(a.l, -a.s+b.l);
        ret.r=max(b.r, a.r-b.s);
        ret.s=a.s+b.s;
        ret.v=max({a.v-b.s, b.v-a.s, a.l+b.r});
        return ret;
    }
    void init(int node, int s, int e) {
        if(s==e) {
            if(t[s-1]=='C') tree[node]={0, 0, 1, 0};
            else tree[node]={1, 1, -1, 1};
            return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        init(lch, s, m), init(rch, m+1, e);
        tree[node]=Merge(tree[lch], tree[rch]);
    }
    Data query(int node, int s, int e, int l, int r) {
        if(l<=s && e<=r) return tree[node];
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(r<=m) return query(lch, s, m, l, r);
        if(l>m) return query(rch, m+1, e, l, r);
        return Merge(query(lch, s, m, l, r), query(rch, m+1, e, l, r));
    }
}T;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>t;
    T.init();
    cin>>q;
    while(q--) {
        int l, r; cin>>l>>r;
        cout<<T.query(l, r)<<"\n";
    }
    return 0;
}

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