oj.uz

Submission #260775

# Submission time Handle Problem Language Result Execution time Memory
260775 2020-08-10T23:40:58 Z thecodingwizard Kralj (COCI16_kralj) C++11
140 / 140
 762 ms 51048 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);

    int n; cin >> n;
    vector<int> adversaries[n];
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        adversaries[x-1].push_back(i);
    }
    int D[n], E[n];
    for (int i = 0; i < n; i++) cin >> D[i];
    for (int i = 0; i < n; i++) cin >> E[i];

    int ctr = 0;
    for (int i = 0; i < n; i++) {
        ctr = max(0, ctr - 1 + (int)adversaries[i].size());
    }
    int startIdx = -1;
    for (int i = 0; i < n; i++) {
        if (ctr == 0) {
            startIdx = i;
            break;
        }
        ctr = ctr - 1 + (int)adversaries[i].size();
        assert(ctr >= 0);
    }

    multiset<int> elves;
    int ans = 0;

    for (int i = 0; i < n; i++) {
        int idx = (startIdx + i) % n;
        for (int elf : adversaries[idx]) {
            elves.insert(E[elf]);
        }
        auto it = elves.upper_bound(D[idx]);
        if (it == elves.end()) {
            elves.erase(elves.begin());
        } else {
            elves.erase(it);
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 41960 KB Output is correct
2 Correct 508 ms 40408 KB Output is correct
3 Correct 644 ms 50540 KB Output is correct
4 Correct 594 ms 51048 KB Output is correct
5 Correct 429 ms 29540 KB Output is correct
6 Correct 348 ms 29304 KB Output is correct
7 Correct 469 ms 33656 KB Output is correct
8 Correct 400 ms 31032 KB Output is correct
9 Correct 496 ms 35508 KB Output is correct
10 Correct 416 ms 31992 KB Output is correct