Submission #311333

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
311333	2020-10-09T23:54:36 Z	super_j6	Kralj (COCI16_kralj)	C++14	56 / 140	750 ms	43540 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(s.empty()) exit(0);
		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	750 ms	37224 KB	Output is correct
2	Correct	447 ms	36584 KB	Output is correct
3	Correct	579 ms	42600 KB	Output is correct
4	Correct	574 ms	43540 KB	Output is correct
5	Incorrect	218 ms	20728 KB	Output isn't correct
6	Incorrect	248 ms	21152 KB	Output isn't correct
7	Incorrect	283 ms	23800 KB	Output isn't correct
8	Incorrect	261 ms	23548 KB	Output isn't correct
9	Incorrect	306 ms	24440 KB	Output isn't correct
10	Incorrect	271 ms	21880 KB	Output isn't correct