oj.uz

Submission #484518

# Submission time Handle Problem Language Result Execution time Memory
484518 2021-11-04T01:31:38 Z hoanghq2004 Election (BOI18_election) C++14
100 / 100
 382 ms 28116 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;

int n, q;
string s;

struct node {
    int L, R;
    int sum;
    int best;
    node operator + (const node& other) const {
        node ret;
        ret.sum = sum + other.sum;
        ret.L = max(L, sum + other.L);
        ret.R = max(other.R, other.sum + R);
        ret.best = max({L + other.R, best + other.sum, sum + other.best});
        return ret;
    }
} st[2000010];

void build(int id, int L, int R) {
    if (L == R) {
        if (s[L - 1] == 'T') st[id] = {1, 1, 1, 1};
        else st[id] = {0, 0, -1, 0};
        return;
    }
    int mid = L + R >> 1;
    build(id * 2, L, mid);
    build(id * 2 + 1, mid + 1, R);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

node get(int id, int L, int R, int u, int v) {
    if (u <= L && R <= v) return st[id];
    int mid = L + R >> 1;
    if (v <= mid) return get(id * 2, L, mid, u, v);
    if (u > mid) return get(id * 2 + 1, mid + 1, R, u, v);
    return get(id * 2, L, mid, u, v) + get(id * 2 + 1, mid + 1, R, u, v);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    cin >> s;
    build(1, 1, n);
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << get(1, 1, n, l, r).best << '\n';
    }
}

Compilation message

election.cpp: In function 'void build(int, int, int)':
election.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = L + R >> 1;
      |               ~~^~~
election.cpp: In function 'node get(int, int, int, int, int)':
election.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = L + R >> 1;
      |               ~~^~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 37 ms 5692 KB Output is correct
7 Correct 38 ms 5700 KB Output is correct
8 Correct 48 ms 5696 KB Output is correct
9 Correct 35 ms 5832 KB Output is correct
10 Correct 40 ms 5680 KB Output is correct
11 Correct 38 ms 5836 KB Output is correct
12 Correct 36 ms 5844 KB Output is correct
13 Correct 40 ms 5864 KB Output is correct
14 Correct 41 ms 5784 KB Output is correct
15 Correct 40 ms 5724 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 37 ms 5692 KB Output is correct
7 Correct 38 ms 5700 KB Output is correct
8 Correct 48 ms 5696 KB Output is correct
9 Correct 35 ms 5832 KB Output is correct
10 Correct 40 ms 5680 KB Output is correct
11 Correct 38 ms 5836 KB Output is correct
12 Correct 36 ms 5844 KB Output is correct
13 Correct 40 ms 5864 KB Output is correct
14 Correct 41 ms 5784 KB Output is correct
15 Correct 40 ms 5724 KB Output is correct
16 Correct 364 ms 26912 KB Output is correct
17 Correct 307 ms 26660 KB Output is correct
18 Correct 318 ms 26764 KB Output is correct
19 Correct 333 ms 26308 KB Output is correct
20 Correct 367 ms 26076 KB Output is correct
21 Correct 382 ms 27836 KB Output is correct
22 Correct 370 ms 27676 KB Output is correct
23 Correct 366 ms 28116 KB Output is correct
24 Correct 370 ms 27696 KB Output is correct
25 Correct 374 ms 27028 KB Output is correct