Submission #1268118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268118		duongquanghai08	Election (BOI18_election)	C++20	82 / 100	34 ms	5188 KiB

election

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Data{
    int sum, prefix, suffix, ans;
}ST[4 * N];
int n, q, a[N];
Data M(Data A, Data B) {
    Data res;
    res.sum = A.sum + B.sum;
    res.prefix = max(A.prefix, A.sum + B.prefix);
    res.suffix = max(B.suffix, B.sum + A.suffix);
    res.ans =  max({A.prefix + B.suffix, A.ans + B.sum, A.sum + B.ans});
    return res;
}
void build(int id, int l, int r) {
    if(l == r) {
        if(a[l] == 1) ST[id] = {-1, 0, 0, 0};
        else ST[id] = {1, 1, 1, 1};
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    ST[id] = M(ST[id * 2], ST[id * 2 + 1]);
}
Data get(int id, int l, int r, int u, int v) {
    if(v < l || u > r) return {0, 0, 0, 0};
    if(u <= l && v >= r) return ST[id];
    int mid = (l + r) / 2;
    return M(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));

}
void Solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        char c; cin >> c;
        if(c == 'C') a[i] = 1;
        else a[i] = -1;
    }
    cin >> q;
    build(1, 1, n);
    while(q--) {
        int l, r; cin >> l >> r;
        cout << get(1, 1, n, l, r).ans << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    Solve();
}

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