Submission #1174697

#TimeUsernameProblemLanguageResultExecution timeMemory
1174697nuutsnoyntonKralj (COCI16_kralj)C++20
0 / 140
386 ms48060 KiB
#include<bits/stdc++.h>

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

	cin >> n;
	ll ind[n + 2], b[n + 2], a[n + 2], cnt[n + 2], cnt1[n + 2];
	for (i = 1; i <= n; i ++) {
		cnt[i] = 0;
	}
	ans = 0;
	for (i = 1; i <= n; i ++) {
		cin >> ind_;
		inde[ind_].push_back(i);
		cnt[ind_] ++;
	}
	
	for (i = 1; i <= n; i ++) cnt1[i]= cnt[i];
	
	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( cnt1[i] <= 1) {
			r = i;
			continue;
		}
		cnt1[i + 1] = cnt1[i + 1] + cnt[i] - 1;
		cnt1[i] = 1;
	}
	if( cnt1[n] <= 1) r = n;
	r ++;
	if ( r == n + 1) r -= n;
	ans = 0;
	tool = 0;
	while ( tool <= n) {
		multiset < ll > MS;
		while(tool <= n) {
			for ( ll X : inde[r]) {
				MS.insert(a[X]);
			}
			if ( MS.empty()) break;
			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;
			tool ++;
		}
		tool ++;
		r ++;
		if ( r > n) r-= n;
	}
	cout << ans << endl;
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...