Submission #59722

#	Time	Username	Problem	Language	Result	Execution time	Memory
59722		model_code	Election (BOI18_election)	C++17	100 / 100	1594 ms	62744 KiB

election

// Andrei-Costin Constantinescu
// O(NlogN)
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 500000 + 5;
int N, v[NMAX];

struct Node {
    int l, r;
    int sum, minSuf;
    Node(int _l = 0, int _r = 0, int _sum = 0, int _minSuf = 0):
        l(_l), r(_r), sum(_sum), minSuf(_minSuf) {}

    static Node singleNode(const int l, const int r, const int val) {
        return Node(l, r, val, min(val, 0));
    }
    friend Node operator+(const Node &arg0, const Node &arg1) {
        return Node(arg0.l, arg1.r, arg0.sum + arg1.sum, min(arg0.minSuf + arg1.sum, arg1.minSuf));
    }
} tree[4 * NMAX];

void build(int node, int l, int r) {
    if (l == r) {
        tree[node] = Node :: singleNode(l, l, 1);
        return ;
    }
    const int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

Node query(int node, int r) {
    if (tree[node].r == r)
        return tree[node];
    const int mid = (tree[node].l + tree[node].r) / 2;
    if (r <= mid)
        return query(2 * node, r);
    else
        return query(2 * node, mid) + query(2 * node + 1, r);
}

void update(int node, int where, int val) {
    if (tree[node].l == tree[node].r) {
        v[where] = val;
        tree[node] = Node :: singleNode(where, where, v[where]);
        return ;
    }
    const int mid = (tree[node].l + tree[node].r) / 2;
    if (where <= mid)
        update(2 * node, where, val);
    else
        update(2 * node + 1, where, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

struct Query {
    int r, pos;
    Query(int _r = 0, int _pos = 0):
        r(_r), pos(_pos) {}
};
vector <Query> queries[NMAX];
int answers[NMAX];

int main() {
    cin >> N;
    assert(1 <= N && N <= 500000);

    string votes;
    cin >> votes;
    assert(static_cast <int>(votes.size()) == N);

    for (int i = 1; i <= N; ++ i) {
        assert(votes[i - 1] == 'C' || votes[i - 1] == 'T');
        v[i] = votes[i - 1] == 'C' ? 1 : -1;
    }
    build(1, 1, N);

    int Q = 0;
    cin >> Q;
    assert(1 <= Q && Q <= 500000);

    for (int i = 1; i <= Q; ++ i) {
        int l, r;
        cin >> l >> r;
        assert(1 <= l && l <= r && r <= N);
        queries[l].emplace_back(r, i);
    }

    vector <int> stk;
    for (int i = N; i; -- i) {
        if (v[i] == -1)
            stk.push_back(i), update(1, i, 0);
        else {
            if (!stk.empty())
                update(1, stk.back(), v[stk.back()] - 1), stk.pop_back();
        }
        for (auto qr: queries[i]) {
            const int l = i, r = qr.r;
            answers[qr.pos] = upper_bound(stk.rbegin(), stk.rend(), r) - stk.rbegin() - query(1, r).minSuf;
        }
    }

    for (int i = 1; i <= Q; ++ i)
        cout << answers[i] << '\n';
    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:101:23: warning: unused variable 'l' [-Wunused-variable]
             const int l = i, r = qr.r;
                       ^

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