Submission #311345

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
311345	2020-10-10T00:31:57 Z	super_j6	Kralj (COCI16_kralj)	C++14	140 / 140	785 ms	43848 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);
		j += v[fnd((x + 1) % n)].size();
		par[x] = (x + 1) % n;
	}
	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

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	785 ms	37608 KB	Output is correct
2	Correct	470 ms	36996 KB	Output is correct
3	Correct	597 ms	43032 KB	Output is correct
4	Correct	615 ms	43848 KB	Output is correct
5	Correct	377 ms	21116 KB	Output is correct
6	Correct	320 ms	21624 KB	Output is correct
7	Correct	433 ms	24440 KB	Output is correct
8	Correct	361 ms	24184 KB	Output is correct
9	Correct	448 ms	24952 KB	Output is correct
10	Correct	402 ms	22308 KB	Output is correct