제출 #645003

#제출 시각아이디문제언어결과실행 시간메모리
645003GusterGoose27Kralj (COCI16_kralj)C++11
140 / 140
499 ms52964 KiB
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5;
int n;
int posses[MAXN];
vector<int> strs[MAXN];
int dstrs[MAXN];
int pre[MAXN];
set<int> opn;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> posses[i]; posses[i]--;
	}
	for (int i = 0; i < n; i++) cin >> dstrs[i];
	for (int i = 0; i < n; i++) {
		int s; cin >> s;
		strs[posses[i]].push_back(s);
	}
	int c = 0;
	int mnpos = 0;
	for (int i = 0; i < n; i++) {
		pre[i] = c;
		c += strs[i].size()-1;
		if (pre[i] < pre[mnpos]) mnpos = i;
	}
	int ans = 0;
	for (int v = mnpos; v < mnpos+n; v++) {
		int j = v%n;
		for (int s: strs[j]) opn.insert(s);
		assert(!opn.empty());
		auto it = opn.upper_bound(dstrs[j]);
		if (it != opn.end()) {
			ans++;
			opn.erase(it);
		}
		else opn.erase(opn.begin());
	}
	cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...