Submission #1232830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232830		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;

void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int> p(n + 1, 0);
    for(int i = 1; i <= n; i++){
        p[i] = p[i - 1] + (s[i - 1] == 'C' ? 1 : -1);
    }
    int logn = 1;
    while((1 << logn) <= n + 1) logn++;
    vector<int> lg(n + 2);
    lg[1] = 0;
    for(int i = 2; i <= n + 1; i++) lg[i] = lg[i / 2] + 1;
    vector<vector<int> > stmin(logn, vector<int>(n + 1));
    vector<vector<int> > stmax(logn, vector<int>(n + 1));
    for(int i = 0; i <= n; i++){
        stmin[0][i] = p[i];
        stmax[0][i] = p[i];
    }
    for(int k = 1;k < logn; k++){
        for(int i = 0; i + (1 << k) <= n + 1; i++){
            stmin[k][i] = min(stmin[k - 1][i], stmin[k - 1][i + (1 << (k - 1))]);
            stmax[k][i] = max(stmax[k - 1][i], stmax[k - 1][i + (1 << (k - 1))]);
        }
    }
    auto get_min = [&](int l, int r){
        int k = lg[r - l + 1];
        return min(stmin[k][l], stmin[k][r - (1 << k) + 1]);
    };
    auto get_max = [&](int l, int r){
        int k = lg[r - l + 1];
        return max(stmax[k][l], stmax[k][r - (1 << k) + 1]);
    };
    int q;
    cin>>q;
    while(q--){
        int l, r;
        cin>>l>>r;
        int min_pref = get_min(l, r);
        int need1 = max(0, p[l - 1] - min_pref);
        int max_pref = get_max(l - 1, r - 1);
        int need2 = max(0, max_pref - p[r]);
        cout<<max(need1, need2)<<'\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