Submission #1232906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232906		edo	Election (BOI18_election)	C++20	100 / 100	348 ms	67088 KiB

election

#include <bits/stdc++.h>
#ifdef LOCAL
#include "../../debug.h"
#else
#define debug(...) ((void)0)
#endif
using namespace std;

using ll  = long long;
// #define int ll
using vi  = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int,int>;

struct Node {
    ll sm;
    ll lz; 
    ll rz;
    ll ans; 
};

Node combine(const Node& a, const Node& b) {
    Node c;
    c.sm = a.sm + b.sm;
    c.lz = min(a.lz, a.sm + b.lz);
    c.rz = min(b.rz, b.sm + a.rz);
    c.ans = min({ a.ans + b.sm, a.sm + b.ans, a.lz + b.rz });
    return c;
}

const Node identity_node = {0, 0, 0, 0};

class SegmentTree {
private:
    vector<Node> tree;
    string s;
    int n;

    void build(int u, int l, int r) {
        if (l == r) {
            if (s[l] == 'C') {
                tree[u].sm = 1;
                tree[u].lz = 0;
                tree[u].rz = 0;
                tree[u].ans = 0;
            } else {
                tree[u].sm = -1;
                tree[u].lz = -1;
                tree[u].rz = -1;
                tree[u].ans = -1;
            }
            return;
        }
        int mid = (l + r) >> 1;
        build(u*2, l, mid);
        build(u*2+1, mid+1, r);
        tree[u] = combine(tree[u*2], tree[u*2+1]);
    }

    Node query(int u, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) {
            return identity_node;
        }
        if (ql <= l && r <= qr) {
            return tree[u];
        }
        int mid = (l + r) >> 1;
        Node left_node = query(u*2, l, mid, ql, qr);
        Node right_node = query(u*2+1, mid+1, r, ql, qr);
        if (qr <= mid) {
            return left_node;
        } else if (ql > mid) {
            return right_node;
        } else {
            return combine(left_node, right_node);
        }
    }

public:
    SegmentTree(const string& str) {
        s = str;
        n = (int)s.size();
        tree.resize(4 * n);
        build(1, 0, n-1);
    }

    int query_range(int l, int r) {
        Node res = query(1, 0, n-1, l, r);
        return -res.ans;
    }
};

void solve() {
    int n; cin >> n;
    string votes; cin >> votes;

    SegmentTree segTree(votes);

    int q; cin >> q;
    while (q--) {
        int L, R;
        cin >> L >> R;
        L--; R--;
        cout << segTree.query_range(L, R) << '\n';
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    while (t--) solve();

    return 0;
}

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