Submission #1076687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076687		codexistent	Kralj (COCI16_kralj)	C++14	140 / 140	565 ms	60856 KiB

kralj

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 500005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)

ll n, pfx[MAXN];
ll d[MAXN], e[MAXN];
vector<ll> ct[MAXN];

int main(){
    cin >> n;
    FOR(i, 1, n) {
        ll x; cin >> x;
        ct[x].push_back(i);
    }
    FOR(i, 1, n) cin >> d[i];
    FOR(i, 1, n) cin >> e[i];

    pair<ll, ll> mn = {0, 1};
    pfx[0] = 0;
    FOR(i, 1, n) {
        pfx[i] = pfx[i - 1] + ct[i].size() - 1;
        if(mn.first >= pfx[i]){
            mn.first = pfx[i];
            mn.second = i % n + 1;
        }
    }

    ll r = 0;
    set<ll> s;
    for(ll i = mn.second, j = 1; j <= n; j++, i = i % n + 1){
        // cout << i << " " << d[i] << endl;
         
        for(ll ei : ct[i]) s.insert(e[ei]);

        if(s.upper_bound(d[i]) != s.end()){
            r++;
            // cout << " a: " << *s.upper_bound(d[i]) << endl;
            s.erase(s.upper_bound(d[i]));
        }else{
            // cout << " b: " << *s.begin() << endl;
            s.erase(s.begin());
        }
    }

    cout << r << endl;
}

• Subtask 1: 140 / 140