제출 #59721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59721		model_code	Election (BOI18_election)	C++17	82 / 100	3052 ms	27468 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(): l(-1), r(-1), sum(-1), minSuf(-1) {}
    Node(int _l, int _r, int _sum, int _minSuf): 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) {
        if (arg0.r == -1)
            return arg1;
        return Node(arg0.l, arg1.r, arg0.sum + arg1.sum, min(arg0.minSuf + arg1.sum, arg1.minSuf));
    }
};

const int SQRT = 500;
Node buckets[NMAX / SQRT + 5];

inline int bucketLeft(int bucket) { return (bucket - 1) * SQRT + 1; }
inline int bucketRight(int bucket) { return min(N, bucket * SQRT); }
inline int whichBucket(int pos) { return (pos - 1) / SQRT + 1; }

void buildBucket(int bucket) {
    const int l = bucketLeft(bucket), r = bucketRight(bucket);
    buckets[bucket] = Node();
    for (int i = l; i <= r; ++ i)
        buckets[bucket] = buckets[bucket] + Node :: singleNode(i, i, v[i]);
}

void updatePos(int where, int addent) {
    v[where] += addent;
    buildBucket(whichBucket(where));
}

Node query(int l, int r) {
    Node ans;
    while (l <= r) {
        const int b = whichBucket(l);
        if (l == bucketLeft(b) && l + SQRT - 1 <= r) {
            ans = ans + buckets[b];
            l += SQRT;
        }
        else {
            ans = ans + Node :: singleNode(l, l, v[l]);
            l += 1;
        }
    }
    return ans;
}

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;
    }

    for (int b = 1; b <= whichBucket(N); ++ b)
        buildBucket(b);

    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);
            updatePos(i, 1);
        }
        else {
            if (!stk.empty()) {
                updatePos(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(l, r).minSuf;
        }
    }

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

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