oj.uz

Submission #956232

# Submission time Handle Problem Language Result Execution time Memory
956232 2024-04-01T11:21:01 Z Iwanttobreakfree Election (BOI18_election) C++17
100 / 100
 484 ms 28136 KB 
#include <bits/stdc++.h>
using namespace std;

const int max_n = 5e5+2;
struct Node{
    int l = 0, r = 0, sum = 0, sol = 0; 
};
Node t[4*max_n];
// a > 0, a tiene t[a] platos sin pagar
Node merge(Node a, Node b) {
    Node ans;
    ans.l = max(a.l, a.sum+b.l);
    ans.r = max(b.r, b.sum+a.r);
    ans.sum = a.sum+b.sum;
    ans.sol = max(a.l+b.r, max(a.sum+b.sol, a.sol+b.sum));
    return ans;
}

Node updateN(Node x, int p) {
    if (p > 0) x.l = x.r = x.sum = x.sol = x.sum+p;
    else x.sum += p;
    return x;
}

void update_p(int n, int l, int r, int p, int x) {
    if (l > p || r < p) return;
    if (l == r) {
        t[n] = updateN(t[n],x);
    }
    else {
        int mid = (r+l)/2;
        update_p(2*n, l, mid, p, x);
        update_p(2*n+1, mid+1, r, p, x);
        t[n] = merge(t[2*n], t[2*n+1]);
        //cout << l << ' ' << r << ' ' << t[n].valL << ' ' << t[n].valR << '\n';
    }
}

Node val(int n, int l, int r, int l2, int r2) {
    if (l > r2 || r < l2) return Node();
    if (l >= l2 && r <= r2) return t[n];
    int mid = (r+l)/2;
    Node L = val(2*n, l, mid, l2, r2);
    Node R = val(2*n+1, mid+1, r, l2, r2);
    return merge(L, R);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    string s;
    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'C') update_p(1, 0, max_n-1, i, -1);
        else update_p(1, 0, max_n-1, i, 1);
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        --x;--y;
        Node ans = val(1, 0, max_n-1, x, y);
        //cout << ans.valL << ' ' << ans.valR << '\n';
        cout << ans.sol << '\n';
    }
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 3 ms 4696 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4440 KB Output is correct
6 Correct 52 ms 9052 KB Output is correct
7 Correct 51 ms 9088 KB Output is correct
8 Correct 50 ms 9040 KB Output is correct
9 Correct 47 ms 9044 KB Output is correct
10 Correct 51 ms 9032 KB Output is correct
11 Correct 52 ms 9044 KB Output is correct
12 Correct 52 ms 9044 KB Output is correct
13 Correct 52 ms 9132 KB Output is correct
14 Correct 58 ms 9436 KB Output is correct
15 Correct 52 ms 9180 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 3 ms 4696 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4440 KB Output is correct
6 Correct 52 ms 9052 KB Output is correct
7 Correct 51 ms 9088 KB Output is correct
8 Correct 50 ms 9040 KB Output is correct
9 Correct 47 ms 9044 KB Output is correct
10 Correct 51 ms 9032 KB Output is correct
11 Correct 52 ms 9044 KB Output is correct
12 Correct 52 ms 9044 KB Output is correct
13 Correct 52 ms 9132 KB Output is correct
14 Correct 58 ms 9436 KB Output is correct
15 Correct 52 ms 9180 KB Output is correct
16 Correct 437 ms 26924 KB Output is correct
17 Correct 384 ms 26472 KB Output is correct
18 Correct 423 ms 27028 KB Output is correct
19 Correct 372 ms 26464 KB Output is correct
20 Correct 442 ms 26080 KB Output is correct
21 Correct 484 ms 28112 KB Output is correct
22 Correct 438 ms 27876 KB Output is correct
23 Correct 431 ms 28040 KB Output is correct
24 Correct 440 ms 28136 KB Output is correct
25 Correct 437 ms 27308 KB Output is correct