Submission #1261513

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

election

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; 
    if (!(cin >> N)) return 0;
    string s; cin >> s;
    s = " " + s; // 1-index

    // Prefix sums P[0..N]
    vector<int> P(N+1, 0);
    for (int i = 1; i <= N; ++i) {
        P[i] = P[i-1] + (s[i] == 'C' ? 1 : -1);
    }

    // Build logs for sparse table
    int M = N + 1; // P has indices [0..N]
    vector<int> lg(M+1, 0);
    for (int i = 2; i <= M; ++i) lg[i] = lg[i/2] + 1;
    int K = lg[M];

    // Sparse tables for min and max over P
    vector<vector<int>> stMin(K+1, vector<int>(M));
    vector<vector<int>> stMax(K+1, vector<int>(M));
    for (int i = 0; i < M; ++i) stMin[0][i] = stMax[0][i] = P[i];
    for (int k = 1; k <= K; ++k) {
        int len = 1 << k;
        int half = len >> 1;
        for (int i = 0; i + len - 1 < M; ++i) {
            stMin[k][i] = min(stMin[k-1][i], stMin[k-1][i+half]);
            stMax[k][i] = max(stMax[k-1][i], stMax[k-1][i+half]);
        }
    }

    auto rmqMin = [&](int L, int R) {
        // query min over P[L..R], with 0 <= L <= R <= N
        int len = R - L + 1;
        int k = lg[len];
        return min(stMin[k][L], stMin[k][R - (1<<k) + 1]);
    };
    auto rmqMax = [&](int L, int R) {
        int len = R - L + 1;
        int k = lg[len];
        return max(stMax[k][L], stMax[k][R - (1<<k) + 1]);
    };

    int Q; cin >> Q;
    while (Q--) {
        int L, R; cin >> L >> R;

        // A = max(0, P[L-1] - min_{k in [L,R]} P[k])
        int minPref = rmqMin(L, R);
        int A = max(0, P[L-1] - minPref);

        // B = max(0, max_{k in [L-1,R-1]} P[k] - P[R])
        int B = 0;
        if (L-1 <= R-1) {
            int maxPref = rmqMax(L-1, R-1);
            B = max(0, maxPref - P[R]);
        }

        cout << max(A, B) << "\n";
    }
    return 0;
}

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