Submission #43473

#	Time	Username	Problem	Language	Result	Execution time	Memory
43473		PowerOfNinjaGo	Teams (IOI15_teams)	C++14	0 / 100	4125 ms	524288 KiB

teams

//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "teams.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 1e5+5;
int n;
int a[maxn], b[maxn];
void init(int N, int A[], int B[])
{
	n = N;
	for(int i = 0; i< N; i++) a[i] = A[i], b[i] = B[i];
}
struct node
{
	int v, prio, cnt;
	node *left, *right;
	node(int _v)
	{
		v = _v;
		prio = (rand()<<16)^rand();
		left = right = NULL;
	}
	void up()
	{
		cnt = 1+(left?left->cnt:0)+(right?right->cnt:0);
	}
};
node* merge(node *L, node *R)
{
	if(!L or !R) return L?L:R;
	if(L->prio > R->prio)
	{
		L->right = merge(L->right, R);
		L->up(); return R;
	}
	else
	{
		R->left = merge(L, R->left);
		R->up(); return R;
	}
}
void splitKey(node *cur, node* &L, node* &R, int key)
{
	L = R = NULL;
	if(!cur) return;
	if(cur->v<= key)
	{
		L = cur;
		splitKey(cur->right, cur->right, R, key);
	}
	else
	{
		R = cur;
		splitKey(cur->left, L, cur->left, key);
	}
	cur->up();
}
void splitCnt(node *cur, node* &L, node* &R, int key)
{
	L = R = NULL;
	if(!cur) return;
	int yo = 1+(cur->left?cur->left->cnt:0);
	if(yo<= key)
	{
		L = cur;
		splitKey(cur->right, cur->right, R, key-yo);
	}
	else
	{
		R = cur;
		splitKey(cur->left, L, cur->left, key);
	}
	cur->up();
}
node *root;
void add(int x)
{
	if(!root) root = new node(x);
	node *temp = NULL;
	splitKey(root, root, temp, x);
	root = merge(root, new node(x));
	root = merge(root, temp);
}
int ask(int x, int num)
{
	node *temp;
	splitKey(root, root, temp, x-1);
	if((temp?temp->cnt:0)< num) return -1;
	node *rubbish;
	splitCnt(temp, rubbish, temp, num);
	root = merge(root, temp);
	return 1;
}
int can(int M, int K[])
{
	int sum = 0;
	for(int i = 0; i< M; i++) sum += K[i];
	if(sum> n) return 0;
	vii vec;
	for(int i = 0; i< n; i++) vec.pb(ii(a[i], b[i]));
	sort(vec.begin(), vec.end());
	sort(K, K+M);
	int ptr = 0;
	for(int i = 0; i< M; i++)
	{
		int here = K[i];
		while(ptr< n && vec[ptr].X<= here) add(vec[ptr++].Y);
		if(ask(here, here) == -1) return 0;
	}
	return 1;
}

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