Submission #1233632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233632		just_crow	Election (BOI18_election)	C++20	0 / 100	149 ms	327680 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct Node {
    int ans;
    int maxp;
    int maxs;
    int sum;

    Node operator+(Node second) {
        Node ret;

        if (ans == INT_MIN and second.ans == INT_MIN) {
            return {INT_MIN, 0, 0, 0};
        } else if (second.ans == INT_MIN) {
            return {ans, maxp, maxs, sum};
        } else if (ans == INT_MIN) {
            return {second.ans, second.maxp, second.maxs, second.sum};
        }

        ret.ans = max(max(sum + second.ans, ans + second.sum), maxp + second.maxs);
        ret.sum = sum + second.sum;
        ret.maxp = max(maxp, sum + second.maxp);
        ret.maxs = max(second.maxs, second.sum + maxs);

        return ret;
    }
};

int n;

vector<char> el(1e9);
vector<Node> segtree(1e9);

unordered_map<char, int> mp = {make_pair('C', -1), make_pair('T', 1)};

void build(int index = 1, int l = 0, int r = n - 1) {
    if (l == r) {
        if (el[l] == 'T') {
            segtree[index] = {1, 1, 1, 1};
        } else {
            segtree[index] = {0, 0, 0, -1};
        }

        return;
    }

    int mid = (l + r) / 2;

    build(index * 2, l, mid);
    build(index * 2 + 1, mid + 1, r);

    segtree[index] = segtree[index * 2] + segtree[index * 2 + 1];
}

Node query(int ql, int qr, int index = 1, int l = 0, int r = n - 1) {
    if (l > qr or r < ql) {
        return {INT_MIN, 0, 0, 0};
    }

    if (l >= ql and r <= qr) {
        return segtree[index];
    }

    int mid = (l + r) / 2;

    return query(ql, qr, index * 2, l, mid) + query(ql, qr, index * 2 + 1, mid + 1, r);
}


signed main() {
    cin >> n;

    for (int i = 0; i < n; ++i) cin >> el[i];

    build();

    int q;

    cin >> q;
    
    while (q--) {
        int a, b;

        cin >> a >> b;

        --a; --b;

        cout << query(a, b).ans << endl;
    }
}

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