Submission #1261515

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

election

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

int main() {
    freopen("elections.in","r",stdin);
    freopen("elections.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; 
    if (!(cin >> N)) return 0;
    string s; cin >> s;
    s = " " + s; 

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

    int M = N + 1; 
    vector<int> lg(M+1, 0);
    for (int i = 2; i <= M; ++i) lg[i] = lg[i/2] + 1;
    int K = lg[M];


    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) {
        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;

        int minPref = rmqMin(L, R);
        int A = max(0, P[L-1] - minPref);

        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;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:5:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |     freopen("elections.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:6:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |     freopen("elections.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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