Submission #1050546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050546		MrAndria	Election (BOI18_election)	C++14	0 / 100	3 ms	2396 KiB

election

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
//#define int long long
int n,q;
string s;
int p[200005],suff[200005],l,r;
pair <int,int> d[200005],d1[200005];
pair <int,int > mx(pair <int,int> x,pair <int,int> y){
    if(x.ff==y.ff){
        return make_pair(x.ff,max(x.ss,y.ss));
    }else{
        return min(x,y);

    }
}
void buildmax(int v,int tl,int tr){
    if(tl==tr){
        d[v]=make_pair(suff[tl],tl);
        return;
    }
    int tm=(tl+tr)/2;
    buildmax(2*v,tl,tm);
    buildmax(2*v+1,tm+1,tr);
    d[v]=mx(d[2*v],d[2*v+1]);
}
pair <int,int> segmax(int v,int tl,int tr,int l,int r){
    if(l>r){
        return make_pair(0,0);
    }
    if(tl==l and tr==r){
        return d[v];

    }
    int tm=(tl+tr)/2;
    return mx(segmax(2*v,tl,tm,l,min(r,tm)),segmax(2*v+1,tm+1,tr,max(l,tm+1),r));
}
void buildmin(int v,int tl,int tr){
    if(tl==tr){
        d1[v]=make_pair(p[tl],tl);
        return;
    }
    int tm=(tl+tr)/2;
    buildmin(2*v,tl,tm);
    buildmin(2*v+1,tm+1,tr);
    d1[v]=min(d1[2*v],d1[2*v+1]);
}
pair <int,int> segmin(int v,int tl,int tr,int l,int r){
    if(l>r){
        return make_pair(INT_MAX,INT_MAX);
    }
    if(tl==l and tr==r){
        // cout<<d1[v].ss<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl;
        return d1[v];
    }
    int tm=(tl+tr)/2;
    // cout<<tm<<endl;
    return min(segmin(2*v,tl,tm,l,min(r,tm)),segmin(2*v+1,tm+1,tr,max(l,tm+1),r));
}
int main(){
    cin>>n;
    cin>>s;
    s=" "+s;
    for(int i=1;i<=n;i++){
        p[i]=p[i-1];
        if(s[i]=='T'){
            p[i]--;
        }else{
            p[i]++;
        }
    }
    for(int i=n;i>=1;i--){
        suff[i]=suff[i+1];
        if(s[i]=='T'){
            suff[i]--;
        }else{
            suff[i]++;
        }
    }
    buildmax(1,1,n);
    buildmin(1,1,n);
    cin>>q;
    // cout<<segmin(1,1,n,3,4).ss<<endl;
    while(q--){
        cin>>l>>r;
        auto pos1=segmin(1,1,n,l,r);
        auto pos2=segmax(1,1,n,l,r);
        // cout<<pos1.ss<<" "<<pos2.ss<<endl;
        if(pos1.ss<pos2.ss){
            cout<<abs(pos1.ff-p[l-1])+abs((pos2.ff-suff[r+1]))<<endl;
            continue;
        }
        auto k=segmin(1,1,n,l,pos2.ss-1);
        // cout<<k.ff<<" "<<k.ss<<endl;
        int fir=abs(min(0,k.ff-p[l-1]));
        if(k.ss==0){
            fir=0;
        }
        k=segmax(1,1,n,pos1.ss+1,r);
        int sec=abs(min(0,(k.ff-suff[r+1])));
        if(k.ss==0){
            sec=0;
        }
        // cout<<fir<<" "<<sec<<endl;
        cout<<fir+sec+max(abs(min(0,pos1.ff-p[l-1]))-fir,abs(min(0,(pos2.ff-suff[r+1])))-sec)<<endl;

    }
}

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