Submission #378806

#	Time	Username	Problem	Language	Result	Execution time	Memory
378806		JerryLiu06	Election (BOI18_election)	C++11	100 / 100	1762 ms	28012 KiB

election

#include <bits/stdc++.h>

using namespace std;

struct Node { int sum, L, R, ans; } tree[2000010];

int N, Q; char S[500010]; 

Node comb(Node A, Node B) {
    Node res; res.sum = A.sum + B.sum; res.L = max(A.L, A.sum + B.L); res.R = max(B.R, A.R + B.sum); 

    res.ans = max(max(A.ans + B.sum, A.sum + B.ans), A.L + B.R); return res;
}
void build(int x, int l, int r) { int mid = (l + r) / 2;
    if (l == r) { if (S[l] == 'T') tree[x] = {1, 1, 1, 1}; else tree[x] = {-1, 0, 0, 0}; return ; }

    build(2 * x, l, mid); build(2 * x + 1, mid + 1, r); tree[x] = comb(tree[2 * x], tree[2 * x + 1]);
}
Node query(int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
    if (r < tl || l > tr) return Node {0, 0, 0, 0}; if (tl <= l && r <= tr) return tree[x]; 

    return comb(query(2 * x, l, mid, tl, tr), query(2 * x + 1, mid + 1, r, tl, tr));
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N; for (int i = 1; i <= N; i++) cin >> S[i]; build(1, 1, N);

    cin >> Q; for (int i = 0; i < Q; i++) { int A, B; cin >> A >> B;
        cout << query(1, 1, N, A, B).ans << endl;
    }
}

Compilation message (stderr)

election.cpp: In function 'Node query(int, int, int, int, int)':
election.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if (r < tl || l > tr) return Node {0, 0, 0, 0}; if (tl <= l && r <= tr) return tree[x];
      |     ^~
election.cpp:20:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |     if (r < tl || l > tr) return Node {0, 0, 0, 0}; if (tl <= l && r <= tr) return tree[x];
      |                                                     ^~

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