Submission #566758

# Submission time Handle Problem Language Result Execution time Memory
566758 2022-05-22T19:54:53 Z Redhood Kralj (COCI16_kralj) C++14
84 / 140
632 ms 52720 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;
    }
    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);
        }
        x++;
        if(x == n)
            x = 0;
    }
    cout << ans;




    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 591 ms 40304 KB Output is correct
2 Correct 427 ms 39620 KB Output is correct
3 Correct 488 ms 46456 KB Output is correct
4 Correct 486 ms 47316 KB Output is correct
5 Incorrect 298 ms 32904 KB Output isn't correct
6 Correct 632 ms 52720 KB Output is correct
7 Incorrect 411 ms 36532 KB Output isn't correct
8 Incorrect 287 ms 34736 KB Output isn't correct
9 Incorrect 366 ms 37780 KB Output isn't correct
10 Correct 308 ms 34180 KB Output is correct