oj.uz

Submission #253836

# Submission time Handle Problem Language Result Execution time Memory
253836 2020-07-28T21:26:32 Z NONAME Kralj (COCI16_kralj) C++14
140 / 140
 753 ms 53224 KB 
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;

const int N = int(5e5) + 500;
const int base = int(1e9) + 7;

int n;
int dwarf[N], elf[N], f[N];
vector <int> g[N];

int main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        --x;

        g[x].push_back(i);
    }
    for (int i = 0; i < n; ++i)
        cin >> dwarf[i];
    for (int i = 0; i < n; ++i)
        cin >> elf[i];

    int p = n - 1;
    for (int i = 0; i < n; ++i) {
        f[i] = f[i - 1] + int(g[i].size()) - 1;

        if (f[i] < f[p])
            p = i;
    }

    //cerr << "\n";
    //for (int i = 0; i < n; ++i, cerr << "\n")
    //for (int j : g[i])
        //cerr << j << " ";
    //cerr << "\n";

    (p += 1) %= n;
    int ans = 0;
    set <int> s;
    s.clear();

    //cerr << p << "\n";

    for (int i = 0; i < n; ++i) {
        for (int j : g[p])
            s.insert(elf[j]);

        auto it = s.upper_bound(dwarf[p]);

        //set <int> se = s;
        //while (!se.empty()) {
            //cerr << *se.begin() << " ";
            //se.erase(se.begin());
        //}
        //cerr << "\n";

        (p += 1) %= n;
        if (it == s.end()) {
            s.erase(s.begin());
            continue;
        }

        s.erase(it);
        ++ans;
    }

    cout << ans << "\n";
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 45764 KB Output is correct
2 Correct 439 ms 44516 KB Output is correct
3 Correct 543 ms 52436 KB Output is correct
4 Correct 600 ms 53224 KB Output is correct
5 Correct 394 ms 32632 KB Output is correct
6 Correct 326 ms 32248 KB Output is correct
7 Correct 451 ms 36216 KB Output is correct
8 Correct 371 ms 34552 KB Output is correct
9 Correct 506 ms 37496 KB Output is correct
10 Correct 376 ms 33912 KB Output is correct