Submission #25850

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
25850	2017-06-24T12:44:14 Z	szawinis	Kralj (COCI16_kralj)	C++14	140 / 140	689 ms	45696 KB

kralj

#include <bits/stdc++.h>
using namespace std;
const int MAX = (5e5)+1;

int n, start, ans, a[MAX], tmp[MAX], d[MAX];
vector<int> e[MAX];
bool mark[MAX];
multiset<int> st;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i], --a[i];
	copy(a, a+n, tmp);
	sort(tmp, tmp+n);
	int curr = 0;
	for(int x: tmp) {
		if(mark[x]) curr = (curr+1)%n;
		else curr = start = x;
		mark[curr] = true;
	}
	for(int i = 0; i < n; i++) cin >> d[i];
	for(int i = 0, x; i < n; i++) cin >> x, e[a[i]].push_back(x);
	for(int z = 0, i = start; z < n; z++, i = (i+1)%n) {
		for(int x: e[i]) st.insert(x);
		auto it = st.lower_bound(d[i]);
		if(it != st.end()) ans++, st.erase(it);
		else st.erase(st.begin());
	}
	cout << ans;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	689 ms	41076 KB	Output is correct
2	Correct	596 ms	40548 KB	Output is correct
3	Correct	476 ms	45168 KB	Output is correct
4	Correct	546 ms	45696 KB	Output is correct
5	Correct	506 ms	23548 KB	Output is correct
6	Correct	326 ms	23944 KB	Output is correct
7	Correct	396 ms	26452 KB	Output is correct
8	Correct	456 ms	26716 KB	Output is correct
9	Correct	646 ms	26716 KB	Output is correct
10	Correct	376 ms	24208 KB	Output is correct