oj.uz

Submission #1011787

# Submission time Handle Problem Language Result Execution time Memory
1011787 2024-07-01T08:22:26 Z gyg Election (BOI18_election) C++17
100 / 100
 1159 ms 33976 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 5;

int n;
array<bool, MAX_N> a;

struct Node {
    int l_open, l_close;
    int r_open, r_close;
    int pairs;
} st[4 * MAX_N];
Node merge(Node x, Node y) {
    int l_del = min(x.l_open, y.l_close);
    x.l_open -= l_del, y.l_close -= l_del;
    int r_del = min(x.r_open, y.r_close);
    x.r_open -= r_del, y.r_close -= r_del;

    x.pairs = min(x.pairs, x.r_open);
    y.pairs = min(y.pairs, y.l_close);

    Node ans = {x.l_open + y.l_open, x.l_close + y.l_close, 
                x.r_open + y.r_open, x.r_close + y.r_close,
                x.pairs + y.pairs};
    if (x.r_open > x.pairs && y.l_close > y.pairs)
        ans.pairs += min(x.r_open - x.pairs, y.l_close - y.pairs);
    return ans;
}
void build(int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        if (a[lo] == 1) st[u].l_open++, st[u].r_close++;
        else st[u].l_close++, st[u].r_open++, st[u].pairs++;
        return;
    }
    int mid = (lo + hi) / 2;
    build(2 * u, lo, mid), build(2 * u + 1, mid + 1, hi);
    st[u] = merge(st[2 * u], st[2 * u + 1]);
}
Node query(int l, int r, int u = 1, int lo = 1, int hi = n) {
    if (r < lo || hi < l) return Node();
    if (l <= lo && hi <= r) return st[u];
    int mid = (lo + hi) / 2;
    return merge(query(l, r, 2 * u, lo, mid), query(l, r, 2 * u + 1, mid + 1, hi));
}

int main() {
    // freopen("elec.in", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char ch; cin >> ch;
        a[i] = (ch == 'C');
    }

    build();

    int q; cin >> q;
    for (int i = 1; i <= q; i++) {
        int l, r; cin >> l >> r;
        Node resp = query(l, r);
        int ans = resp.l_close + resp.r_open - resp.pairs;
        cout << ans << '\n';
    }
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2396 KB Output is correct
2 Correct 4 ms 2392 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 131 ms 9872 KB Output is correct
7 Correct 124 ms 9808 KB Output is correct
8 Correct 137 ms 9920 KB Output is correct
9 Correct 129 ms 9812 KB Output is correct
10 Correct 136 ms 9764 KB Output is correct
11 Correct 179 ms 10064 KB Output is correct
12 Correct 138 ms 10068 KB Output is correct
13 Correct 149 ms 10148 KB Output is correct
14 Correct 154 ms 9932 KB Output is correct
15 Correct 136 ms 10056 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2396 KB Output is correct
2 Correct 4 ms 2392 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 131 ms 9872 KB Output is correct
7 Correct 124 ms 9808 KB Output is correct
8 Correct 137 ms 9920 KB Output is correct
9 Correct 129 ms 9812 KB Output is correct
10 Correct 136 ms 9764 KB Output is correct
11 Correct 179 ms 10064 KB Output is correct
12 Correct 138 ms 10068 KB Output is correct
13 Correct 149 ms 10148 KB Output is correct
14 Correct 154 ms 9932 KB Output is correct
15 Correct 136 ms 10056 KB Output is correct
16 Correct 1147 ms 33104 KB Output is correct
17 Correct 1159 ms 32608 KB Output is correct
18 Correct 1142 ms 32816 KB Output is correct
19 Correct 996 ms 32412 KB Output is correct
20 Correct 1106 ms 32132 KB Output is correct
21 Correct 1056 ms 33976 KB Output is correct
22 Correct 1052 ms 33640 KB Output is correct
23 Correct 1067 ms 33872 KB Output is correct
24 Correct 1033 ms 33700 KB Output is correct
25 Correct 1092 ms 33104 KB Output is correct