Submission #366538

#TimeUsernameProblemLanguageResultExecution timeMemory
366538FatihSolakKralj (COCI16_kralj)C++17
140 / 140
742 ms51172 KiB
#include <bits/stdc++.h>
#define N 500005
using namespace std;
int pos[N],d[N];
vector<int> ep[N];
multiset<int> p;
void solve(){
    int n;
    cin >> n;   
    for(int i=0;i<n;i++){
        cin >> pos[i];
        pos[i]--;
    }
    for(int i=0;i<n;i++){
        cin >> d[i];
    }
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        ep[pos[i]].push_back(a);
    }
    int st = N,mini = N;
    int cnt = 0;
    for(int i=0;i<n;i++){
        cnt += ep[i].size();
        if(cnt - i < mini){
            st = i;
            mini = cnt-i;
        }
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        st = (st+1)%n;
        for(auto u:ep[st]){
            p.insert(u);
        }
        auto it = p.upper_bound(d[st]);
        if(it == p.end()){
            p.erase(p.begin());
        }
        else{
            p.erase(it);
            ans++;
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}
#Verdict Execution timeMemoryGrader output
Fetching results...