oj.uz

Submission #366538

# Submission time Handle Problem Language Result Execution time Memory
366538 2021-02-14T11:00:16 Z FatihSolak Kralj (COCI16_kralj) C++17
140 / 140
 742 ms 51172 KB 
#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
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 742 ms 44132 KB Output is correct
2 Correct 430 ms 43108 KB Output is correct
3 Correct 561 ms 50532 KB Output is correct
4 Correct 562 ms 51172 KB Output is correct
5 Correct 353 ms 30700 KB Output is correct
6 Correct 303 ms 30444 KB Output is correct
7 Correct 401 ms 34284 KB Output is correct
8 Correct 327 ms 32748 KB Output is correct
9 Correct 421 ms 35564 KB Output is correct
10 Correct 357 ms 31980 KB Output is correct