oj.uz

답안 #311331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311331 2020-10-09T23:48:54 Z super_j6 Kralj (COCI16_kralj) C++14
56 / 140
 779 ms 62328 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);
		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

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