Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
71753055 Practice:
CP_Sucks
1315D - 12 C++17 (GCC 7-32) Accepted 171 ms 6252 KB 2020-02-24 11:57:25 2020-02-24 11:57:25
→ Source
//dhruv
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ffor(i,n) for(int i = 0;i < (n); ++i)
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define ff first
#define ss second


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int n;
    cin >> n;
    vpii a(n);
    ffor(i,n) cin >> a[i].ff;
    ffor(i,n) cin >> a[i].ss;
    sort(all(a));

    priority_queue<int> pq;
    int ans = 0,cur_sum = 0;
    int pos = 0,cur_lev = 0;

    // pq has all duplicats 
    // Overall Complexity is O(nlogn) i add duplicate once and remove once also
    while(!pq.empty() || pos < n){
    	if(!pq.empty()){
    		// There are some duplicates
    		// Don't change the one with max value
    		cur_sum -= pq.top();
    		pq.pop();
    		// this place is full move to next value
    		++cur_lev;
    		// total jumps i will have to make up by 1
    		ans += cur_sum;
    	}else{
    		// no duplicate so far make the current level jump 
    		cur_lev = a[pos].ff;
    	}

    	int new_pos = pos;
    	// Add any duplicates in this place 
    	while(new_pos < n && (a[new_pos].ff == cur_lev)){
    		pq.push(a[new_pos].ss);
    		cur_sum += a[new_pos].ss;
    		++new_pos;
    	}
    	pos = new_pos;
    }

    cout << ans;
}		
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details