oj.uz

Submission #59721

# Submission time Handle Problem Language Result Execution time Memory
59721 2018-07-23T00:38:19 Z model_code Election (BOI18_election) C++17
82 / 100
 3000 ms 27468 KB 
// 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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12152 KB Output is correct
2 Correct 21 ms 12264 KB Output is correct
3 Correct 26 ms 12264 KB Output is correct
4 Correct 24 ms 12400 KB Output is correct
5 Correct 26 ms 12400 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12152 KB Output is correct
2 Correct 21 ms 12264 KB Output is correct
3 Correct 26 ms 12264 KB Output is correct
4 Correct 24 ms 12400 KB Output is correct
5 Correct 26 ms 12400 KB Output is correct
6 Correct 519 ms 14720 KB Output is correct
7 Correct 474 ms 14720 KB Output is correct
8 Correct 447 ms 14720 KB Output is correct
9 Correct 416 ms 14720 KB Output is correct
10 Correct 407 ms 14720 KB Output is correct
11 Correct 537 ms 15104 KB Output is correct
12 Correct 395 ms 15104 KB Output is correct
13 Correct 472 ms 15152 KB Output is correct
14 Correct 351 ms 15152 KB Output is correct
15 Correct 457 ms 15152 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12152 KB Output is correct
2 Correct 21 ms 12264 KB Output is correct
3 Correct 26 ms 12264 KB Output is correct
4 Correct 24 ms 12400 KB Output is correct
5 Correct 26 ms 12400 KB Output is correct
6 Correct 519 ms 14720 KB Output is correct
7 Correct 474 ms 14720 KB Output is correct
8 Correct 447 ms 14720 KB Output is correct
9 Correct 416 ms 14720 KB Output is correct
10 Correct 407 ms 14720 KB Output is correct
11 Correct 537 ms 15104 KB Output is correct
12 Correct 395 ms 15104 KB Output is correct
13 Correct 472 ms 15152 KB Output is correct
14 Correct 351 ms 15152 KB Output is correct
15 Correct 457 ms 15152 KB Output is correct
16 Execution timed out 3052 ms 27468 KB Time limit exceeded
17 Halted 0 ms 0 KB -