Submission #645003

#	Time	Username	Problem	Language	Result	Execution time	Memory
645003		GusterGoose27	Kralj (COCI16_kralj)	C++11	140 / 140	499 ms	52964 KiB

kralj

#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";
}

• Subtask 1: 140 / 140