oj.uz

Submission #951248

# Submission time Handle Problem Language Result Execution time Memory
951248 2024-03-21T13:39:16 Z vjudge1 Election (BOI18_election) C++17
0 / 100
 1 ms 604 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -