oj.uz

Submission #860847

# Submission time Handle Problem Language Result Execution time Memory
860847 2023-10-14T15:56:54 Z Blagoj Election (BOI18_election) C++17
0 / 100
 11 ms 63068 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]);
    }

    ll get(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return 0;
        if (i <= l && r <= j) return sgt[k].ans;
        int m = (l + r) / 2;
        return 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) << endl;
    }
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 63068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 63068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 63068 KB Output isn't correct
2 Halted 0 ms 0 KB -