Submission #311331

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
311331	2020-10-09T23:48:54 Z	super_j6	Kralj (COCI16_kralj)	C++14	56 / 140	779 ms	62328 KB

kralj

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 500000;
int n;
int a[mxn], b[mxn], par[mxn];
vector<int> v[mxn];
set<int> s;

int fnd(int x){
	return x == par[x] ? x : par[x] = fnd(par[x]);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	for(int i = 0; i < n; i++) cin >> b[i];
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		v[--b[i]].push_back(x);
		par[i] = i;
	}
	
	int st = n - 1;
	for(int i = 0; i < n; st--)
	for(int j = v[st].size(); i < n && j; i++, j--){
		int x = fnd(st);
		par[x] = (x + 1) % n;
		j += v[(x + 1) % n].size();
	}
	st++;
	
	int ret = 0;
	for(int i = 0; i < n; i++){
		int x = (st + i) % n;
		for(int j : v[x]) s.insert(j);
		if(a[x] < *prev(s.end())){
			s.erase(s.lower_bound(a[x]));
			ret++;
		}else{
			s.erase(s.begin());
		}
	}
	
	cout << ret << endl;
	
	return 0;
}

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	779 ms	45760 KB	Output is correct
2	Correct	462 ms	44648 KB	Output is correct
3	Correct	573 ms	52460 KB	Output is correct
4	Correct	578 ms	53096 KB	Output is correct
5	Runtime error	253 ms	53624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	272 ms	53624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	305 ms	60536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	274 ms	58488 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	322 ms	62328 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	328 ms	56228 KB	Execution killed with signal 11 (could be triggered by violating memory limits)