oj.uz

Submission #1076687

# Submission time Handle Problem Language Result Execution time Memory
1076687 2024-08-26T15:34:46 Z codexistent Kralj (COCI16_kralj) C++14
140 / 140
 565 ms 60856 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 52176 KB Output is correct
2 Correct 370 ms 50636 KB Output is correct
3 Correct 512 ms 60408 KB Output is correct
4 Correct 509 ms 60856 KB Output is correct
5 Correct 435 ms 40788 KB Output is correct
6 Correct 372 ms 40020 KB Output is correct
7 Correct 460 ms 43348 KB Output is correct
8 Correct 395 ms 40532 KB Output is correct
9 Correct 482 ms 45132 KB Output is correct
10 Correct 449 ms 42660 KB Output is correct