Submission #1131046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131046		A_M_Namdar	Election (BOI18_election)	C++20	100 / 100	617 ms	70956 KiB

election

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
int n, q, a[N], sum[N], ans[N];
vector<int> pos[N + N];
vector<pair<int, int>> vec[N];
struct node {
        int maxi, lazy;
} seg[N << 2];

void build(int l, int r, int id) {
        if (r - l == 1) {
                seg[id].maxi = sum[l];
                return;
        }
        int mid = (l + r) / 2;
        build(l, mid, id << 1), build(mid, r, id << 1 | 1);
        seg[id].maxi = max(seg[id << 1].maxi, seg[id << 1 | 1].maxi);
}

void shift(int id) {
        seg[id << 1].lazy += seg[id].lazy, seg[id << 1 | 1].lazy += seg[id].lazy;
        seg[id << 1].maxi += seg[id].lazy, seg[id << 1 | 1].maxi += seg[id].lazy;
        seg[id].lazy = 0;
}

void add(int l1, int r1, int l2, int r2, int v, int id) {
        if (l1 >= r2 || r1 <= l2) return;
        if (l1 >= l2 && r1 <= r2) {
                seg[id].lazy += v, seg[id].maxi += v;
                return;
        }
        shift(id);
        int mid = (l1 + r1) / 2;
        add(l1, mid, l2, r2, v, id << 1), add(mid, r1, l2, r2, v, id << 1 | 1);
        seg[id].maxi = max(seg[id << 1].maxi, seg[id << 1 | 1].maxi);
}

int get(int l, int r, int ind, int id) {
        if (l > ind || r <= ind) return 0;
        if (r - l == 1) return seg[id].lazy;
        shift(id);
        int mid = (l + r) / 2;
        return get(l, mid, ind, id << 1) + get(mid, r, ind, id << 1 | 1);
}

int get_max(int l1, int r1, int l2, int r2, int id) {
        if (l1 >= r2 || r1 <= l2) return -1e9;
        if (l1 >= l2 && r1 <= r2) return seg[id].maxi;
        shift(id);
        int mid = (l1 + r1) / 2;
        return max(get_max(l1, mid, l2, r2, id << 1), get_max(mid, r1, l2, r2, id << 1 | 1));
}

void input() {
        cin >> n;
        for (int i = 0; i < n; i++) {
                char c;
                cin >> c;
                a[i] = (c == 'C') - (c != 'C');
                sum[i] = (i? sum[i - 1]: 0) + a[i];
                pos[sum[i] + N].push_back(i);
        }
        cin >> q;
        for (int i = 0; i < q; i++) {
                int l, r;
                cin >> l >> r;
                vec[l - 1].push_back({r, i});
        }
}

void solve() {
        build(0, n, 1);
        for (int i = n - 1; i >= 0; i--) {
                if (a[i] == 1) {
                        int x = (i? sum[i - 1]: 0);
                        int tmp = upper_bound(pos[x + N].begin(), pos[x + N].end(), i) - pos[x + N].begin();
                        if (tmp < (int)pos[x + N].size()) {
                                add(0, n, pos[x + N][tmp], n, -1, 1);
//                              cout << pos[x + N][tmp] << ' ' << n << ' ' << -1 << '\n';
                        }
                }
                else {
                        add(0, n, i, n, 1, 1);
//                      cout << i << ' ' << n << ' ' << 1 << '\n';
                }

                for (pair<int, int> tmp: vec[i]) {
//                      ans[tmp.second] = get(0, n, tmp.first - 1, 1) + max(0, get_max(0, n, i, tmp.first, 1) - sum[tmp.first - 1] - get(0, n, tmp.first - 1, 1));
                        ans[tmp.second] = get_max(0, n, i, tmp.first, 1) - sum[tmp.first - 1];
//                      cout <<  get_max(0, n, i, tmp.first, 1) << ' ' << sum[tmp.first - 1] << '\n';
                }
        }
}

void output() {
        for (int i = 0; i < q; i++) {
                cout << ans[i];
                if (i + 1 < q) cout << '\n';
        }
}

int main() {
        ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
        input();
        solve();
        output();
}

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18