Submission #566766

#	Time	Username	Problem	Language	Result	Execution time	Memory
566766		Redhood	Kralj (COCI16_kralj)	C++14	140 / 140	606 ms	47396 KiB

kralj

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