Submission #875827

#	Time	Username	Problem	Language	Result	Execution time	Memory
875827		1075508020060209tc	Election (BOI18_election)	C++14	28 / 100	3037 ms	9816 KiB

election

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int Q;
string s;
int ar[500005];
int ps[500005];
int sf[500005];
int nn;

void solve(){
int ret=0;
int lps=0;
for(int i=1;i<=nn;i++){
    ret=max(ret,max(0ll,sf[i])+lps);
lps=max(lps,ps[i]);
}
cout<<ret<<"\n";
}

signed main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        if(s[i-1]=='T'){
            ar[i]=1;
        }else{
            ar[i]=-1;
        }
    }
    cin>>Q;
    while(Q--){
        int l;int r;
        cin>>l>>r;
        nn=r-l+1;
        for(int i=l;i<=r;i++){
            ps[i-l+1]=ar[i];
            ps[i-l+1]+=ps[i-l+1-1];
        }
        sf[nn+1]=0;
        for(int i=r;i>=l;i--){
            sf[i-l+1]=ar[i];
            sf[i-l+1]+=sf[i-l+1+1];
        }
        /*
        for(int i=1;i<=nn;i++){
            cout<<ps[i]<<" ";
        }cout<<"\n";
        for(int i=1;i<=nn;i++){
            cout<<sf[i]<<" ";
        }cout<<"\n";*/
        solve();
    }

}

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