Submission #951401

#	Time	Username	Problem	Language	Result	Execution time	Memory
951401		vjudge1	Election (BOI18_election)	C++17	0 / 100	2 ms	856 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 + 1);
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        a[i] = 1 - 2 * (c == 'T');
    }
    vector<int> pre(n + 1), suf(n + 2);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + a[i];
    }
    for (int i = n; i; i--) {
        suf[i] = suf[i + 1] + a[i];
    }

    vector<int> pos(2 * n + 5, n + 1);
    vector<vector<int>> nxt(n + 2, vector<int>(M, n + 1));
    for (int i = n; i >= 0; i--) {
        int tar = pre[i] - 1 - (a[i] == 1);
        nxt[i][0] = pos[tar + n + 2];
        pos[pre[i] + n + 2] = i;
    }
    for (int j = 1; j < M; j++) {
        for (int i = 0; i <= n; i++) {
            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
        }
    }

    pos.assign(2 * n + 5, 0);
    vector<vector<int>> prev(n + 2, vector<int>(M));
    for (int i = 1; i <= n + 1; i++) {
        int tar = suf[i] - 1 - (a[i] == 1);
        prev[i][0] = pos[tar + n + 2];
        pos[suf[i] + n + 2] = i;
    }
    for (int j = 1; j < M; j++) {
        for (int i = 1; i <= n + 1; i++) {
            prev[i][j] = prev[prev[i][j - 1]][j - 1];
        }
    }

    auto get_l_info = [&](int l, int r) -> array<int, 2> {
        if (a[l] == 1)
            l = nxt[l][0];
        int cnt = 0;
        for (int i = M - 1; i >= 0; i--) {
            if (nxt[l][i] <= r) {
                l = nxt[l][i];
                cnt += 1 << i;
            }
        }
        return {l, cnt + (l <= r)};
    };
    auto get_r_info = [&](int l, int r) -> array<int, 2> {
        if (a[r] == 1)
            r = prev[r][0];
        int cnt = 0;
        for (int i = M - 1; i >= 0; i--) {
            if (prev[r][i] >= l) {
                r = prev[r][i];
                cnt += 1 << i;
            }
        }
        return {r, cnt + (l <= r)};
    };

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        auto l1 = get_l_info(l, r);
        auto r1 = get_r_info(l, r);
        auto l2 = get_l_info(l, min(l1[0], r1[0]) - 1);
        auto r2 = get_r_info(max(l1[0], r1[0]) + 1, r);
        int ans = l2[1] + r2[1];
        ans += max(l1[1] - l2[1], r1[1] - r2[1]);
        cout << ans << "\n";
    }
}

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