답안 #51846 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51846	2018-06-21T16:24:42 Z	radoslav11	팀들 (IOI15_teams)	C++14	100 / 100	2160 ms	538808 KB

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

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.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	12024 KB	Output is correct
2	Correct	12 ms	12136 KB	Output is correct
3	Correct	12 ms	12248 KB	Output is correct
4	Correct	14 ms	12360 KB	Output is correct
5	Correct	12 ms	12476 KB	Output is correct
6	Correct	13 ms	12476 KB	Output is correct
7	Correct	12 ms	12628 KB	Output is correct
8	Correct	12 ms	12628 KB	Output is correct
9	Correct	11 ms	12628 KB	Output is correct
10	Correct	12 ms	12628 KB	Output is correct
11	Correct	12 ms	12628 KB	Output is correct
12	Correct	12 ms	12628 KB	Output is correct
13	Correct	13 ms	12628 KB	Output is correct
14	Correct	12 ms	12636 KB	Output is correct
15	Correct	12 ms	12636 KB	Output is correct
16	Correct	12 ms	12636 KB	Output is correct
17	Correct	12 ms	12636 KB	Output is correct
18	Correct	12 ms	12636 KB	Output is correct
19	Correct	12 ms	12640 KB	Output is correct
20	Correct	11 ms	12640 KB	Output is correct
21	Correct	12 ms	12640 KB	Output is correct
22	Correct	12 ms	12640 KB	Output is correct
23	Correct	11 ms	12656 KB	Output is correct
24	Correct	12 ms	12656 KB	Output is correct
25	Correct	11 ms	12656 KB	Output is correct
26	Correct	12 ms	12656 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	186 ms	72768 KB	Output is correct
2	Correct	181 ms	73744 KB	Output is correct
3	Correct	184 ms	75004 KB	Output is correct
4	Correct	182 ms	76580 KB	Output is correct
5	Correct	130 ms	76580 KB	Output is correct
6	Correct	124 ms	76776 KB	Output is correct
7	Correct	128 ms	77308 KB	Output is correct
8	Correct	136 ms	78052 KB	Output is correct
9	Correct	156 ms	98948 KB	Output is correct
10	Correct	136 ms	98948 KB	Output is correct
11	Correct	128 ms	98948 KB	Output is correct
12	Correct	117 ms	98948 KB	Output is correct
13	Correct	130 ms	98948 KB	Output is correct
14	Correct	142 ms	98948 KB	Output is correct
15	Correct	178 ms	98948 KB	Output is correct
16	Correct	169 ms	98948 KB	Output is correct
17	Correct	125 ms	98948 KB	Output is correct
18	Correct	124 ms	98948 KB	Output is correct

Subtask #3
43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	197 ms	98948 KB	Output is correct
2	Correct	188 ms	98948 KB	Output is correct
3	Correct	386 ms	98948 KB	Output is correct
4	Correct	210 ms	98948 KB	Output is correct
5	Correct	157 ms	98948 KB	Output is correct
6	Correct	156 ms	98948 KB	Output is correct
7	Correct	128 ms	98948 KB	Output is correct
8	Correct	151 ms	98948 KB	Output is correct
9	Correct	157 ms	118804 KB	Output is correct
10	Correct	159 ms	118804 KB	Output is correct
11	Correct	157 ms	118804 KB	Output is correct
12	Correct	152 ms	118804 KB	Output is correct
13	Correct	231 ms	118804 KB	Output is correct
14	Correct	393 ms	118804 KB	Output is correct
15	Correct	198 ms	118804 KB	Output is correct
16	Correct	198 ms	118804 KB	Output is correct
17	Correct	152 ms	118804 KB	Output is correct
18	Correct	157 ms	118804 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1209 ms	390604 KB	Output is correct
2	Correct	1251 ms	398076 KB	Output is correct
3	Correct	2059 ms	412364 KB	Output is correct
4	Correct	1316 ms	413352 KB	Output is correct
5	Correct	824 ms	413352 KB	Output is correct
6	Correct	823 ms	417168 KB	Output is correct
7	Correct	696 ms	421096 KB	Output is correct
8	Correct	704 ms	426408 KB	Output is correct
9	Correct	861 ms	538808 KB	Output is correct
10	Correct	745 ms	538808 KB	Output is correct
11	Correct	736 ms	538808 KB	Output is correct
12	Correct	780 ms	538808 KB	Output is correct
13	Correct	1161 ms	538808 KB	Output is correct
14	Correct	2160 ms	538808 KB	Output is correct
15	Correct	1152 ms	538808 KB	Output is correct
16	Correct	1145 ms	538808 KB	Output is correct
17	Correct	756 ms	538808 KB	Output is correct
18	Correct	742 ms	538808 KB	Output is correct

답안 #51846

Compilation message

Subtask #1 21.0 / 21.0

Subtask #2 13.0 / 13.0

Subtask #3 43.0 / 43.0

Subtask #4 23.0 / 23.0

Subtask #1
21.0 / 21.0

Subtask #2
13.0 / 13.0

Subtask #3
43.0 / 43.0

Subtask #4
23.0 / 23.0