Submission #951247

#	Time	Username	Problem	Language	Result	Execution time	Memory
951247		vjudge1	Election (BOI18_election)	C++17	0 / 100	1 ms	604 KiB

election

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5e5 + 5;
const int M = 19;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        a[i] = 1 - 2 * (c == 'T');
    }
    vector<int> pre(n + 1), suf(n + 2);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + a[i];
    }
    for (int i = n - 1; i >= 0; i--) {
        suf[i + 1] = suf[i + 2] + a[i];
    }

    int sp1[n + 1][M], sp2[n + 1][M];
    for (int i = 1; i <= n; i++) {
        sp1[i][0] = pre[i], sp2[i][0] = suf[i];
    }
    for (int j = 1; j < M; j++) {
        for (int i = 1; i <= n; i++) {
            int nxt = min(n, i + (1 << (j - 1)));
            sp1[i][j] = min(sp1[i][j - 1], sp1[nxt][j - 1]);
            sp2[i][j] = min(sp2[i][j - 1], sp2[nxt][j - 1]);
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int lg = 31 - __builtin_clz(r - l + 1);
        int a1 = min(sp1[l][lg], sp1[r - (1 << lg) + 1][lg]) - pre[l - 1];
        int a2 = min(sp2[l][lg], sp2[r - (1 << lg) + 1][lg]) - suf[r + 1];
        cout << max(0, -min(a1, a2)) << "\n";
    }
}

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