oj.uz

Submission #645003

# Submission time Handle Problem Language Result Execution time Memory
645003 2022-09-25T19:48:41 Z GusterGoose27 Kralj (COCI16_kralj) C++11
140 / 140
 499 ms 52964 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 45632 KB Output is correct
2 Correct 325 ms 44688 KB Output is correct
3 Correct 417 ms 52412 KB Output is correct
4 Correct 412 ms 52964 KB Output is correct
5 Correct 270 ms 32336 KB Output is correct
6 Correct 234 ms 32248 KB Output is correct
7 Correct 310 ms 36072 KB Output is correct
8 Correct 258 ms 34440 KB Output is correct
9 Correct 323 ms 37364 KB Output is correct
10 Correct 295 ms 33768 KB Output is correct