Submission #1232896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232896		Adnanboi	Election (BOI18_election)	C++20	0 / 100	1 ms	576 KiB

election

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int lg2[500005];
vector<vector<int> > stF, stB;
vector<int> P, PR;

int rmq(const vector<vector<int> >& st, int L, int R){
    int j = lg2[R - L + 1];
    return min(st[j][L], st[j][R - (1 << j) + 1]);
}

void solve(){
    int N; string S;
    cin>>N>>S;
    P.assign(N + 1, 0);
    PR.assign(N + 2, 0);
    for(int i = 1; i <= N; i++){
        P[i] = P[i - 1]+(S[i - 1] == 'C' ? 1 : -1);
    }
    for(int i = N; i>= 1; i--){
        PR[N - i + 1] = PR[N - i] + (S[i - 1] == 'C' ? 1 : -1);
    }
    lg2[1] = 0;
    for(int i = 2; i<= N; i++) lg2[i] = lg2[i / 2] + 1;
    int K = lg2[N] + 1;
    stF.assign(K, vector<int>(N + 1));
    stB.assign(K, vector<int>(N + 1));
    for(int i = 1; i<= N; i++){
        stF[0][i] = P[i];
        stB[0][i] = PR[i];
    }
    for(int j = 1; j < K; j++){
        for(int i = 1; i + (1 << j) - 1 <= N; i++){
            stF[j][i] = min(stF[j - 1][i], stF[j - 1][i + (1 << (j - 1))]);
            stB[j][i] = min(stB[j - 1][i], stB[j - 1][i + (1 << (j - 1))]);
        }
    }
    int Q; 
    cin>>Q;
    while(Q--){
        int L, R; 
        cin>>L>>R;
        int baseF = P[L - 1];
        int mnF = rmq(stF, L, R);
        int delF = max(0, baseF-mnF);
        int Lp = N - R + 1, Rp = N - L + 1;
        int baseB = PR[Lp - 1];
        int mnB = rmq(stB, Lp, Rp);
        int delB = max(0, baseB - mnB);
        cout<<max(delF, delB)<<"\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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