Submission #1093550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093550		KhoaDuy	Election (BOI18_election)	C++14	0 / 100	4 ms	348 KiB

election

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=5e5;
struct node{
    int sum=0;
    int Minpref=0;
    int Minsuf=0;
};
node iden;
node seg[4*MAXN]={0};
node TT(node left,node right){
    node pa;
    pa.sum=left.sum+right.sum;
    pa.Minpref=min(left.Minpref,left.sum+right.Minpref);
    pa.Minsuf=min(right.Minsuf,right.sum+left.Minsuf);
    return pa;
}
void build(int v,int TL,int TR,string &s){
    if(TL==TR){
        if(s[TL]=='C'){
            seg[v].sum=1;
            seg[v].Minpref=1;
            seg[v].Minsuf=1;
        }
        else{
            seg[v].sum=-1;
            seg[v].Minpref=-1;
            seg[v].Minsuf=-1;
        }
        return;
    }
    int TM=((TL+TR)>>1);
    build(v<<1,TL,TM,s);
    build((v<<1)|1,TM+1,TR,s);
    seg[v]=TT(seg[v<<1],seg[(v<<1)|1]);
}
node query(int v,int TL,int TR,int l,int r){
    if(l>TR||r<TL){
        return iden;
    }
    if(l<=TL&&TR<=r){
        return seg[v];
    }
    int TM=((TL+TR)>>1);
    return TT(query(v<<1,TL,TM,l,r),query((v<<1)|1,TM+1,TR,l,r));
}
signed main(){
    node iden;
    iden.sum=0;
    iden.Minpref=0;
    iden.Minsuf=0;
    int n;
    cin >> n;
    string s;
    cin >> s;
    build(1,0,n-1,s);
    int q;
    cin >> q;
    while(q--){
        int l,r;
        cin >> l >> r;
        l--,r--;
        node curr=query(1,0,n-1,l,r);
        cout << max({0LL,-curr.Minpref,-(curr.sum+curr.Minsuf)}) << endl;
    }
}

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