Submission #1108868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108868		0pt1mus23	Election (BOI18_election)	C++14	100 / 100	454 ms	44512 KiB

election

// fast.cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
int nxt(){ int x;cin>>x; return x; }

const int mod = 1e9 +7, sze = 5e5 +10, inf = LLONG_MAX, LG = 20;
string s;
int n;
struct st{
    int sum=0;
    int pf=0;
    int sf=0;
    int res=0;
} T[sze*4];

st combine(st a,st b){
    st c;
    c.sum = a.sum + b.sum;
    c.pf = max(a.pf, a.sum + b.pf);
    c.sf = max(b.sf, b.sum + a.sf);
    c.res=max( { a.pf  + b.sf , a.res + b.sum, a.sum + b.res });
    return c;
}
void build(int node,int l,int r){
    if(l==r){
        if(s[l]=='C'){
            T[node]={-1,0,0,0};
        }
        else{
            T[node]={1,1,1,1};
        }
        return ;
    }
    int mid = (l+r)/2;
    build(2*node,l,mid);
    build(2*node +1,mid+1,r);
    T[node]=combine(T[node*2],T[node*2 +1]);
}
st qry(int l,int r,int node=1,int lx=0,int rx=n-1){
    if(l>rx || r<lx){
        return {0,0,0,0};
    }
    if(lx>=l && rx<=r){
        return T[node];
    }
    int mid = (lx+rx)/2;
    return combine(qry(l,r,2*node ,lx,mid), qry(l,r,2*node +1,mid+1,rx));

}
void rush(){
    cin>>n;
    cin>>s;
    build(1,0,n-1);
    int q;
    cin>>q;
    while(q--){
        int l=nxt()-1,r=nxt()-1;
        cout<<qry(l,r,1,0,n-1).res<<endl;
    }
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        rush();
    }
 
    return 0;
}

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