Submission #374886

#	Time	Username	Problem	Language	Result	Execution time	Memory
374886		GioChkhaidze	Kralj (COCI16_kralj)	C++14	140 / 140	899 ms	60932 KiB

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 (stderr)

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 / 140