Submission #51846

#	Time	Username	Problem	Language	Result	Execution time	Memory
51846		radoslav11	Teams (IOI15_teams)	C++14	100 / 100	2160 ms	538808 KiB

teams

#include <bits/stdc++.h>
//#include "Lgrader.cpp"
#define endl '\n'

using namespace std;
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
const int MAXN = (int)5e5 + 42;

struct node
{
	int sz;
	node *l, *r;

	node() { sz = 0; l = r = nullptr; }
	node(int val) { sz = val; l = r = nullptr; }

	void pushup()
	{
		sz = 0;
		if(l) sz += l->sz;
		if(r) sz += r->sz;
	}
};

using pnode = node*;


bool keep;
/*
list<pnode> keep_for_erase;

pnode new_node(int sz = 0)
{
	auto it = new node(sz);
	if(keep) keep_for_erase.push_back(it);
	return it;
}*/

pnode ptr_list[MAXN * 10];
int psz = 0;

pnode new_node(int sz = 0)
{
	if(!keep) return new node(sz);
	if(!ptr_list[psz]) ptr_list[psz] = new node();
	ptr_list[psz]->l = ptr_list[psz]->r = nullptr;
	ptr_list[psz]->sz = sz;
	return ptr_list[psz++];
}

inline int size(pnode it) { return it ? it->sz : 0; }

pnode build_tree(int l, int r)
{
	if(l == r) 
		return new_node(0);
	
	int mid = (l + r) >> 1;

	pnode ret = new_node();
	ret->l = build_tree(l, mid);
	ret->r = build_tree(mid + 1, r);

	ret->pushup();
	return ret;
}

pnode remove_less(int pos, int l, int r, pnode tmp)
{
	if(!tmp) return nullptr;
	if(l == r)
		return nullptr;

	int mid = (l + r) >> 1;
	pnode ret = new_node();
	
	if(mid < pos) 
	{
		ret->l = nullptr;
		ret->r = remove_less(pos, mid + 1, r, tmp ? tmp->r : nullptr);
	}
	else 
	{
		ret->l = remove_less(pos, l, mid, tmp ? tmp->l : nullptr);
		ret->r = tmp ? tmp->r : nullptr;
	}

	ret->pushup();
	return ret;
}

pnode add_val(int pos, int l, int r, pnode tmp)
{
	if(pos < l) return tmp;
	if(pos > r) return tmp;
	if(l == r) return new_node(size(tmp) + 1);
		
	int mid = (l + r) >> 1;
	
	pnode ret = new node();
	ret->l = add_val(pos, l, mid, tmp ? tmp->l : nullptr);
	ret->r = add_val(pos, mid + 1, r, tmp ? tmp->r : nullptr);

	ret->pushup();
	return ret;
}

int n;
vector<int> li[MAXN];
pnode root[MAXN];

void init(int n, int a[], int b[])
{
	::n = n;
	root[0] = nullptr;

	for(int i = 1; i <= n; i++) li[i].clear();
	for(int i = 0; i < n; i++)
		li[a[i]].push_back(b[i]);

	pnode last = root[0];
	for(int i = 1; i <= n; i++)
	{
		root[i] = last;
		for(int x: li[i])  
			root[i] = last = add_val(x, 1, n, last);
		
		//if(i != 1) root[i] = last = remove_less(i - 1, 1, n, last);
	}
}

pnode used;

int size_diff_l(pnode used, pnode actual)
{
	int sz = actual ? size(actual->l) : 0;
	if(used) sz -= size(used->l);
	return sz;
}

int Kth_val;

inline pnode L(pnode it) { return it ? it->l : nullptr; }
inline pnode R(pnode it) { return it ? it->r : nullptr; }

pnode get_new_used(int start, int l, int r, pnode used, pnode tmp)
{
	if(size(tmp) - size(used) <= 0) return used;
	if(r < start) return nullptr;
	if(Kth_val == 0) return used;
	if(l == r)
	{
		int q = min(Kth_val, size(tmp) - size(used));
		Kth_val -= q;
		return new_node(size(used) + q);
	}

	int mid = (l + r) >> 1;
	pnode ret = new_node();
	
	if(start <= l)
	{
		if(size(tmp) - size(used) <= Kth_val)
		{
			Kth_val -= size(tmp) - size(used);
			return tmp;
		}

		if(size_diff_l(used, tmp) >= Kth_val)
		{
			ret->l = get_new_used(start, l, mid, L(used), L(tmp));
			ret->r = R(used);
		}
		else
		{
			ret->l = L(tmp);
			Kth_val -= size_diff_l(used, tmp);
			ret->r = get_new_used(start, mid + 1, r, R(used), R(tmp));
		}
	}
	else
	{
		ret->l = get_new_used(start, l, mid, L(used), L(tmp));
		if(Kth_val) ret->r = get_new_used(start, mid + 1, r, R(used), R(tmp));
		else ret->r = R(used);
	}

	ret->pushup();
	return ret;
}
int can(int m, int k[])
{
	int sum = 0;
	for(int i = 0; i < m; i++)
	{
		sum += k[i];
		if(sum > n) return 0;
	}

	int actual_psz = psz;
	used = nullptr;	
	keep = 1;

	sort(k, k + m);
	for(int i = 0; i < m; i++)
	{
		int K = k[i];
		//if(K != 1) used = remove_less(K - 1, 1, n, used);
		
		Kth_val = K;
		used = get_new_used(K, 1, n, used, root[K]);

		if(Kth_val) 
		{
			keep = 0;
			psz = actual_psz;
			return 0;	
		}
	}

	
	keep = 0;
	/*
	while(!keep_for_erase.empty())
	{
		auto it = keep_for_erase.back();
		keep_for_erase.pop_back();
		free(it);
		//delete it;
	}*/

	//while(psz > actual_psz) free(ptr_list[--psz]);
	psz = actual_psz;


	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:113:34: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void init(int n, int a[], int b[])
                                  ^
teams.cpp:109:5: note: shadowed declaration is here
 int n;
     ^
teams.cpp: In function 'int size_diff_l(pnode, pnode)':
teams.cpp:135:41: warning: declaration of 'used' shadows a global declaration [-Wshadow]
 int size_diff_l(pnode used, pnode actual)
                                         ^
teams.cpp:133:7: note: shadowed declaration is here
 pnode used;
       ^~~~
teams.cpp: In function 'node* get_new_used(int, int, int, pnode, pnode)':
teams.cpp:147:66: warning: declaration of 'used' shadows a global declaration [-Wshadow]
 pnode get_new_used(int start, int l, int r, pnode used, pnode tmp)
                                                                  ^
teams.cpp:133:7: note: shadowed declaration is here
 pnode used;
       ^~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23