oj.uz

답안 #311345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311345 2020-10-10T00:31:57 Z super_j6 Kralj (COCI16_kralj) C++14
140 / 140
 785 ms 43848 KB 
#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

# 결과 실행 시간 메모리 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