제출 #1311353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311353		matere	Election (BOI18_election)	C++20	0 / 100	4 ms	3128 KiB

election

#include<bits/stdc++.h>
using namespace std;
int n,q,lg[500005];
pair<int,int>pref[2][21][500005];
pair<int,int> findmax(int l,int r,int tp){
    if(r<l) return {1e9,0};
    int pw=lg[r-l+1];
    pair<int,int>ans=min(pref[tp][pw][l],pref[tp][pw][r-(1<<pw)+1]);
    // if(ans.first>0) return {0,0};
    return ans;
}
int main(){
    cin>>n;
    string s;
    cin>>s;
    for(int i=2;i<=500000;i++) lg[i]=lg[i/2]+1;
    for(int i=1;i<=n;i++){
        pref[0][0][i].first=pref[0][0][i-1].first;
        if(s[i-1]=='T') pref[0][0][i].first--;
        else pref[0][0][i].first++;
        pref[0][0][i].second=i;
    }
    for(int i=n;i>=1;i--){
        pref[1][0][i].first=pref[1][0][i+1].first;
        if(s[i-1]=='T') pref[1][0][i].first--;
        else pref[1][0][i].first++;
        pref[1][0][i].second=-i;
    }
    for(int pw=1;pw<=19;pw++){
        for(int i=1;i<=n;i++){
            for(int nm:{0,1}){
                pref[nm][pw][i]=min(pref[nm][pw-1][i],pref[nm][pw-1][min(n,i+(1<<(pw-1)))]);
            }
        }
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        pair<int,int> ind0=findmax(l,r,0),sh0=findmax(ind0.second+1,r,1);
        pair<int,int> ind1=findmax(l,r,1),sh1=findmax(l,-ind1.second-1,0);
        ind1.second*=-1;
        sh0.second*=-1;
        ind0.first-=pref[0][0][l-1].first;
        sh1.first-=pref[0][0][l-1].first;
        ind1.first-=pref[1][0][r+1].first;
        sh0.first-=pref[1][0][r+1].first;
        ind0.first=min(ind0.first,0);
        ind1.first=min(ind1.first,0);
        sh0.first=min(sh0.first,0);
        sh1.first=min(sh1.first,0);
        // cout<<"{"<<ind0.first<<","<<ind0.second<<"}"<<' ';
        // cout<<"{"<<sh0.first<<","<<sh0.second<<"}"<<'|';
        // cout<<"{"<<ind1.first<<","<<ind1.second<<"}"<<' ';
        // cout<<"{"<<sh1.first<<","<<sh1.second<<"}"<<endl;
        // cout<<l<<'-'<<r<<' ';
        cout<<-(min(ind0.first-sh1.first,ind1.first-sh0.first)+sh0.first+sh1.first)<<endl;
    }
}

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