Submission #374886

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
374886	2021-03-08T12:46:04 Z	GioChkhaidze	Kralj (COCI16_kralj)	C++14	140 / 140	899 ms	60932 KB

kralj

#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)
      |                   ~~^~~~~~~~~~~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	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