oj.uz

답안 #1050410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1050410 2024-08-09T09:14:04 Z MrAndria Election (BOI18_election) C++14
0 / 100
 4 ms 2396 KB 
#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];
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]=max(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 max(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);
        
        // cout<<k.ff<<" "<<k.ss<<endl;

        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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -