Submission #1174711

#TimeUsernameProblemLanguageResultExecution timeMemory
1174711nuutsnoyntonKralj (COCI16_kralj)C++20
140 / 140
484 ms51300 KiB
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 5e5 + 2;
vector < ll > inde[N];
ll a[N], b[N], cnt[N];
int main() {
	ll n, m, r,lo, hi,can, tool, mid, x, y, i, j, ans, t, ind_;

	cin >> n;

	ans = 0;
	for (i = 1; i <= n; i ++) {
		cin >> ind_;
		inde[ind_].push_back(i);
		cnt[ind_] ++;
	}
	
	
	for (i = 1; i <= n; i ++) cin >> b[i];
	for (i = 1; i <= n; i ++) cin >> a[i];
	
	r = -1;
	for (i = 1; i < n; i ++) {
		if( cnt[i] <= 1) {
			r = i;
			continue;
		}
		cnt[i + 1] = cnt[i + 1] + cnt[i] - 1;
		cnt[i] = 1;
	}
	if( cnt[n] <= 1) r = n;
	if ( r == -1) while(1);
	r ++;
	if ( r == n + 1) r -= n;
	
	ans = 0;
	tool = 0;
	
	multiset < ll > MS;
	while(tool < n) {
		tool ++;
		for ( ll X : inde[r]) {
			MS.insert(a[X]);
		}
		auto P = MS.upper_bound(b[r]);
		if ( P == MS.end()) {
			auto S = MS.begin();
			MS.erase(S);
		}
		else {
			ans ++;
			MS.erase(P);
		}
		r ++;
		if ( r > n)  r-= n;
	}
	cout << ans << endl;
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...