oj.uz

Submission #1026915

# Submission time Handle Problem Language Result Execution time Memory
1026915 2024-07-18T13:40:12 Z phoenix Election (BOI18_election) C++17
100 / 100
 318 ms 28132 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 19);

struct node {
    int s;
    int l;
    int r;
    int d;
} tr[2 * N];

node calc(node l, node r) {
    node res;
    res.s = l.s + r.s;
    res.l = max(l.l, l.s + r.l);
    res.r = max(r.r, r.s + l.r);
    res.d = max({l.s + r.d, l.d + r.s, l.l + r.r});
    return res;
}

int n;
string s;

void build(int l = 0, int r = N - 1, int v = 1) {
    if (l == r) {
        int c = (l > n || s[l] != 'C');
        tr[v].s = (c ? +1 : -1);
        tr[v].l = tr[v].r = tr[v].d;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, 2 * v);
    build(mid + 1, r, 2 * v + 1);
    tr[v] = calc(tr[2 * v], tr[2 * v + 1]);
}

node query(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr) 
        return node();
    if (ql <= l && r <= qr)
        return tr[v];
    int mid = (l + r) / 2;
    return calc(query(ql, qr, l, mid, 2 * v), query(ql, qr, mid + 1, r, 2 * v + 1));
}

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

    cin >> n;
    cin >> s;

    build();    

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        node t = query(l, r);
        cout << t.d << '\n';
    }
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16732 KB Output is correct
2 Correct 12 ms 16732 KB Output is correct
3 Correct 11 ms 16732 KB Output is correct
4 Correct 11 ms 16780 KB Output is correct
5 Correct 11 ms 16732 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16732 KB Output is correct
2 Correct 12 ms 16732 KB Output is correct
3 Correct 11 ms 16732 KB Output is correct
4 Correct 11 ms 16780 KB Output is correct
5 Correct 11 ms 16732 KB Output is correct
6 Correct 43 ms 18204 KB Output is correct
7 Correct 43 ms 18004 KB Output is correct
8 Correct 43 ms 18112 KB Output is correct
9 Correct 40 ms 18132 KB Output is correct
10 Correct 49 ms 18008 KB Output is correct
11 Correct 53 ms 18248 KB Output is correct
12 Correct 50 ms 18260 KB Output is correct
13 Correct 51 ms 18272 KB Output is correct
14 Correct 45 ms 18268 KB Output is correct
15 Correct 45 ms 18004 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16732 KB Output is correct
2 Correct 12 ms 16732 KB Output is correct
3 Correct 11 ms 16732 KB Output is correct
4 Correct 11 ms 16780 KB Output is correct
5 Correct 11 ms 16732 KB Output is correct
6 Correct 43 ms 18204 KB Output is correct
7 Correct 43 ms 18004 KB Output is correct
8 Correct 43 ms 18112 KB Output is correct
9 Correct 40 ms 18132 KB Output is correct
10 Correct 49 ms 18008 KB Output is correct
11 Correct 53 ms 18248 KB Output is correct
12 Correct 50 ms 18260 KB Output is correct
13 Correct 51 ms 18272 KB Output is correct
14 Correct 45 ms 18268 KB Output is correct
15 Correct 45 ms 18004 KB Output is correct
16 Correct 318 ms 27100 KB Output is correct
17 Correct 267 ms 26700 KB Output is correct
18 Correct 286 ms 26852 KB Output is correct
19 Correct 240 ms 26340 KB Output is correct
20 Correct 290 ms 26164 KB Output is correct
21 Correct 301 ms 27924 KB Output is correct
22 Correct 298 ms 27884 KB Output is correct
23 Correct 303 ms 28132 KB Output is correct
24 Correct 297 ms 27764 KB Output is correct
25 Correct 285 ms 27112 KB Output is correct