제출 #1138893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138893		woohyun_jng	Election (BOI18_election)	C++20	0 / 100	1 ms	576 KiB

election

#include <bits/stdc++.h>
#define int long long

#define MAX 600000
using namespace std;

typedef array<int, 4> tp; // sm, lmax, rmax,  mx;

tp merge(tp X, tp Y) {
    tp res = {X[0] + Y[0], X[1], Y[2], 0};
    bool fX = false, fY = false;
    if (X[0] + Y[1] >= X[1])
        fX = true, res[1] = X[0] + Y[1];
    if (X[2] + Y[0] >= Y[2])
        fY = true, res[2] = X[2] + Y[0];
    if (fX && fY)
        res[3] = X[2] + Y[1];
    return res;
}

int A[MAX];
tp tree[MAX * 4];

void init(int n, int s, int e) {
    if (s == e)
        tree[n] = {A[s], A[s], A[s], A[s]};
    else {
        int m = s + e >> 1;
        init(n << 1, s, m), init(n << 1 | 1, m + 1, e);
        tree[n] = merge(tree[n << 1], tree[n << 1 | 1]);
    }
}

tp query(int n, int s, int e, int l, int r) {
    if (r < s || e < l)
        return {0, 0, 0, 0};
    else if (l <= s && e <= r)
        return tree[n];
    else {
        int m = s + e >> 1;
        return merge(
            query(n << 1, s, m, l, r),
            query(n << 1 | 1, m + 1, e, l, r));
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N, Q, L, R, ans;
    tp res;
    string S;

    cin >> N >> S;
    for (int i = 1; i <= N; i++)
        A[i] = S[i - 1] == 'T' ? 1 : -1;

    init(1, 1, N);

    cin >> Q;
    while (Q--) {
        cin >> L >> R;
        res = query(1, 1, N, L, R);
        ans = max(0ll, res[1]) + max(0ll, res[2]);
        if (res[3] != 0)
            ans = max({0ll, res[1], res[2]});
        cout << ans << '\n';
    }

    return 0;
}

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