oj.uz

Submission #378806

# Submission time Handle Problem Language Result Execution time Memory
378806 2021-03-17T04:53:18 Z JerryLiu06 Election (BOI18_election) C++11
100 / 100
 1762 ms 28012 KB 
#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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 364 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 364 KB Output is correct
6 Correct 228 ms 4716 KB Output is correct
7 Correct 215 ms 5740 KB Output is correct
8 Correct 216 ms 5740 KB Output is correct
9 Correct 207 ms 5868 KB Output is correct
10 Correct 221 ms 5740 KB Output is correct
11 Correct 223 ms 5868 KB Output is correct
12 Correct 223 ms 5868 KB Output is correct
13 Correct 216 ms 5996 KB Output is correct
14 Correct 218 ms 5868 KB Output is correct
15 Correct 226 ms 5868 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 364 KB Output is correct
6 Correct 228 ms 4716 KB Output is correct
7 Correct 215 ms 5740 KB Output is correct
8 Correct 216 ms 5740 KB Output is correct
9 Correct 207 ms 5868 KB Output is correct
10 Correct 221 ms 5740 KB Output is correct
11 Correct 223 ms 5868 KB Output is correct
12 Correct 223 ms 5868 KB Output is correct
13 Correct 216 ms 5996 KB Output is correct
14 Correct 218 ms 5868 KB Output is correct
15 Correct 226 ms 5868 KB Output is correct
16 Correct 1750 ms 27116 KB Output is correct
17 Correct 1657 ms 26680 KB Output is correct
18 Correct 1674 ms 26860 KB Output is correct
19 Correct 1580 ms 26532 KB Output is correct
20 Correct 1759 ms 26268 KB Output is correct
21 Correct 1744 ms 28012 KB Output is correct
22 Correct 1754 ms 27848 KB Output is correct
23 Correct 1762 ms 27932 KB Output is correct
24 Correct 1751 ms 27812 KB Output is correct
25 Correct 1733 ms 27156 KB Output is correct