Submission #1232899

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

election

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int N;
vector<int> P, PR;
vector<int> segF, segB;

void buildF(int v, int l, int r) {
    if(l == r){
        segF[v] = P[l];
    } 
    else{
        int m = (l + r) / 2;
        buildF(v * 2, l, m);
        buildF(v * 2 + 1, m + 1, r);
        segF[v] = min(segF[v * 2], segF[v * 2 + 1]);
    }
}

int queryF(int v, int l, int r, int ql, int qr) {
    if(ql > r || qr < l) return INT_MAX;
    if(ql <= l && r <= qr) return segF[v];
    int m = (l + r) / 2;
    return min(queryF(v * 2, l, m, ql, qr),
        		   queryF(v * 2 + 1, m + 1, r, ql, qr)
    );
}

void buildB(int v, int l, int r) {
    if(l == r) {
        segB[v] = PR[l];
    } 
    else{
        int m = (l + r) / 2;
        buildB(v * 2, l, m);
        buildB(v * 2 + 1, m + 1, r);
        segB[v] = min(segB[v * 2], segB[v * 2 + 1]);
    }
}

int queryB(int v, int l, int r, int ql, int qr) {
    if(ql > r || qr < l) return INT_MAX;
    if(ql <= l && r <= qr) return segB[v];
    int m = (l + r) / 2;
    return min(queryB(v * 2, l, m, ql, qr),
        		   queryB(v * 2 + 1, m + 1, r, ql, qr)
    );
}

void solve(){
    cin>>N;
    string S;
    cin>>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);
    }
    segF.assign(4 * N, INT_MAX);
    segB.assign(4 * N, INT_MAX);
    buildF(1, 1, N);
    buildB(1, 1, N);
    int Q;
    cin>>Q;
    while(Q--){
        int L, R;
        cin>>L>>R;
        int baseF = P[L - 1];
        int mnF = queryF(1, 1, N, L, R);
        int delF = max(0, baseF - mnF);
        int Lp = N - R + 1;
        int Rp = N - L + 1;
        int baseB = PR[Lp - 1];
        int mnB = queryB(1, 1, N, 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