Submission #875855

#	Time	Username	Problem	Language	Result	Execution time	Memory
875855		1075508020060209tc	Election (BOI18_election)	C++14	100 / 100	1292 ms	68936 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];
struct SGTR{
int l;int r;
int mn;
int psmn;int sfmn;
int sum;
}tr[2000006];

void pull(int nw){
tr[nw].sum=tr[nw*2].sum+tr[nw*2+1].sum;
tr[nw].psmn=min(tr[nw*2].psmn,tr[nw*2].sum+tr[nw*2+1].psmn);
tr[nw].sfmn=min(tr[nw*2+1].sfmn,tr[nw*2+1].sum+tr[nw*2].sfmn);
tr[nw].mn=min({tr[nw*2].mn,tr[nw*2+1].mn,tr[nw*2].sfmn+tr[nw*2+1].psmn});
}

void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
if(l==r){
    tr[nw].sum=ar[l];
    tr[nw].psmn=min(ar[l],0ll);
    tr[nw].sfmn=min(ar[l],0ll);
    tr[nw].mn=min(ar[l],0ll);
    return;
}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);buildtr(nw*2+1,mi+1,r);
pull(nw);
}
int psmn;
int ans;
void qry(int nw,int l,int r){
if(tr[nw].l>=l&&tr[nw].r<=r){
  //  cout<<nw<<" "<<tr[nw].l<<" "<<tr[nw].r<<" "<<tr[nw].psmn<<" "<<tr[nw].sfmn<<" "<<tr[nw].sum<<"\n";
    ans=min(ans,tr[nw].mn);
    ans=min(ans,tr[nw].psmn+psmn);
    psmn=min(psmn+tr[nw].sum,tr[nw].sfmn);
    return;
}
if(tr[nw].l>r||tr[nw].r<l){return;}
qry(nw*2,l,r);qry(nw*2+1,l,r);
}




signed main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        if(s[i-1]=='T'){
            ar[i]=1;
        }else{
            ar[i]=-1;
        }
        ps[i]=ar[i]+ps[i-1];
    }
    buildtr(1,1,n);



    cin>>Q;
    while(Q--){
        int l;int r;
        cin>>l>>r;
        ans=0;
        psmn=0;
        qry(1,l,r);
     //   cout<<ps[r]-ps[l-1]<<" "<<ans<<" ";
        cout<<ps[r]-ps[l-1]-ans<<"\n";
    }

}

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