답안 #374886

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
374886 2021-03-08T12:46:04 Z GioChkhaidze Kralj (COCI16_kralj) C++14
140 / 140
899 ms 60932 KB
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

int n;
vector < int > v[N];
multiset < int > St; 
int a[N], A[N], B[N];
int S[2 * N], C[2 * N];

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	
	for (int i = 1; i <= n; ++i) {
		cin >> B[i];
	}
	
	for (int i = 1; i <= n; ++i) {
		cin >> A[i];
		v[a[i]].push_back(A[i]);
	}
	
	int j = 0;
	for (int i = 1; i <= n; ++i) {
		for (int k = 0; k < v[i].size(); ++k) 
			++j, C[j] = i, S[j] = S[j - 1] + 1;
		++j, C[j] = -i, S[j] = S[j - 1] - 1;
	}

	int id = 0;
	S[0] = 0;
	for (int i = 1; i <= n + n; ++i) {
		if (S[i] < S[id]) id = i;
	}
	
	int ans = 0;
	for (int i = id + 1; i <= n + n; ++i) {
		if (C[i] < 0) {
			int Si = -C[i];
			assert(St.size() > 0);
			if (St.upper_bound(B[Si]) != St.end()) 
				++ans, St.erase(St.upper_bound(B[Si]));
					else 
				St.erase(St.find(*St.begin()));	
		}
			else {
			St.insert(v[C[i]].back());
			v[C[i]].pop_back();
		}
	}
	
	for (int i = 1; i <= id; ++i) {
		if (C[i] < 0) {
			int Si = -C[i];
			assert(St.size() > 0);
			if (St.upper_bound(B[Si]) != St.end()) 
				++ans, St.erase(St.upper_bound(B[Si]));
					else 
				St.erase(St.find(*St.begin()));	
		}
			else {
			St.insert(v[C[i]].back());
			v[C[i]].pop_back();
		}
	}

	assert(St.size() == 0);
	cout << ans << "\n";
}

Compilation message

kralj.cpp:13:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main () {
      |       ^
kralj.cpp: In function 'int main()':
kralj.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (int k = 0; k < v[i].size(); ++k)
      |                   ~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 899 ms 52068 KB Output is correct
2 Correct 477 ms 50660 KB Output is correct
3 Correct 595 ms 60132 KB Output is correct
4 Correct 617 ms 60932 KB Output is correct
5 Correct 404 ms 39532 KB Output is correct
6 Correct 323 ms 39276 KB Output is correct
7 Correct 471 ms 43516 KB Output is correct
8 Correct 363 ms 41196 KB Output is correct
9 Correct 498 ms 45292 KB Output is correct
10 Correct 383 ms 41836 KB Output is correct