oj.uz

Submission #860849

# Submission time Handle Problem Language Result Execution time Memory
860849 2023-10-14T15:59:21 Z Blagoj Election (BOI18_election) C++17
28 / 100
 50 ms 64836 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

struct Node {
    ll sum, pref, suff, ans;
};

int n, arr[(int) 5e5 + 10];

struct SegmentTree {
    vector<Node> sgt;

    SegmentTree(int n) {
        sgt.resize(4 * n);
    }

    Node merge(Node a, Node b) {
        return { a.sum + b.sum, max(a.pref, a.sum + b.pref), max(b.suff, a.suff + b.sum), max({0LL, a.pref + b.suff, a.sum + b.ans, a.ans + b.sum}) };
    }

    void build(int k = 1, int l = 0, int r = n - 1) {
        if (l == r) {
            sgt[k] = { arr[l], arr[l], arr[l], max(arr[l], 0) };
            return;
        }
        int m = (l + r) / 2;
        build(k * 2, l, m);
        build(k * 2 + 1, m + 1, r);
        sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
    }

    Node get(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return {0, 0, 0, 0};
        if (i <= l && r <= j) return sgt[k];
        int m = (l + r) / 2;
        return merge(get(k * 2, l, m, i, j), get(k * 2 + 1, m + 1, r, i, j));
    }

} sgt(5e5);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) arr[i] = (s[i] == 'C' ? -1 : 1);
    sgt.build();
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << sgt.get(1, 0, n - 1, --x, --y).ans << endl;
    }
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 63064 KB Output is correct
2 Correct 10 ms 63068 KB Output is correct
3 Correct 11 ms 63052 KB Output is correct
4 Correct 10 ms 63112 KB Output is correct
5 Correct 11 ms 62924 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 63064 KB Output is correct
2 Correct 10 ms 63068 KB Output is correct
3 Correct 11 ms 63052 KB Output is correct
4 Correct 10 ms 63112 KB Output is correct
5 Correct 11 ms 62924 KB Output is correct
6 Correct 48 ms 64596 KB Output is correct
7 Correct 46 ms 64556 KB Output is correct
8 Correct 46 ms 64452 KB Output is correct
9 Correct 42 ms 64604 KB Output is correct
10 Correct 47 ms 64452 KB Output is correct
11 Correct 50 ms 64768 KB Output is correct
12 Correct 50 ms 64592 KB Output is correct
13 Correct 50 ms 64836 KB Output is correct
14 Incorrect 48 ms 64792 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 63064 KB Output is correct
2 Correct 10 ms 63068 KB Output is correct
3 Correct 11 ms 63052 KB Output is correct
4 Correct 10 ms 63112 KB Output is correct
5 Correct 11 ms 62924 KB Output is correct
6 Correct 48 ms 64596 KB Output is correct
7 Correct 46 ms 64556 KB Output is correct
8 Correct 46 ms 64452 KB Output is correct
9 Correct 42 ms 64604 KB Output is correct
10 Correct 47 ms 64452 KB Output is correct
11 Correct 50 ms 64768 KB Output is correct
12 Correct 50 ms 64592 KB Output is correct
13 Correct 50 ms 64836 KB Output is correct
14 Incorrect 48 ms 64792 KB Output isn't correct
15 Halted 0 ms 0 KB -