oj.uz

Submission #566766

# Submission time Handle Problem Language Result Execution time Memory
566766 2022-05-22T20:03:30 Z Redhood Kralj (COCI16_kralj) C++14
140 / 140
 606 ms 47396 KB 
#include <bits/stdc++.h>

using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef long double ld;

const int N = (int)5e5 + 10;


vector < int > atcur[N];
int main()
{
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int n;
    cin >> n;
    vector < int > a(n);
    vector < int > c(n);
    for(auto &i : a)
        cin >> i, --i, c[i]++;


    for(int i = 0; i < n; ++i){
        atcur[a[i]].pb(i);
    }
    vector < int > p(n) , v(n);
    for(auto &i : p)cin >> i;
    for(auto &i : v)cin >> i;


    /// я не буду нахуй спать
    vector < int > pref(n);
    pref[0] = c[0];
    for(int i = 1; i < n; ++i){
        pref[i] = pref[i - 1] + c[i];
    }
    /// damn
    for(int i = 0; i < n; ++i){
        pref[i] -= (i + 1);
    }
    int psmn = min_element(all(pref)) - pref.begin();
    /// okay

    int x = psmn + 1;
    if(x == n)
        x = 0;
    int ans = 0;
    set < int > st;
    for(int it=0;it<n;++it){
        for(auto &u : atcur[x]){
            st.insert(v[u]);
        }
        auto itt = st.lower_bound(p[x]);
        if(itt != st.end()){
            ans++;
            st.erase(itt);
        }else
            st.erase(st.begin());
        x++;
        if(x == n)
            x = 0;
    }
    cout << ans;




    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 40316 KB Output is correct
2 Correct 326 ms 39652 KB Output is correct
3 Correct 509 ms 46324 KB Output is correct
4 Correct 443 ms 47396 KB Output is correct
5 Correct 312 ms 24188 KB Output is correct
6 Correct 246 ms 24596 KB Output is correct
7 Correct 391 ms 27592 KB Output is correct
8 Correct 282 ms 26828 KB Output is correct
9 Correct 398 ms 28360 KB Output is correct
10 Correct 276 ms 25928 KB Output is correct