Submission #253836

#	Time	Username	Problem	Language	Result	Execution time	Memory
253836		NONAME	Kralj (COCI16_kralj)	C++14	140 / 140	753 ms	53224 KiB

kralj

#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 / 140