Submission #584832

#	Time	Username	Problem	Language	Result	Execution time	Memory
584832		AngusRitossa	Teams (IOI15_teams)	C++14	77 / 100	4054 ms	500048 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct ptreenode
{
	int left, right, val; // val = num
};
ptreenode ptree[20000000];
int upto;
void pupdate(int node, int curr, int oldcurr, int cstart = 0, int cend = 500010)
{
	if (cstart == cend)
	{
		ptree[curr].val = ptree[oldcurr].val+1;
		return;
	}
	int mid = (cstart+cend)/2;
	if (node <= mid)
	{
		ptree[curr].left = ++upto;
		ptree[curr].right = ptree[oldcurr].right;
		pupdate(node, ptree[curr].left, ptree[oldcurr].left, cstart, mid);
	}
	else
	{
		ptree[curr].right = ++upto;
		ptree[curr].left = ptree[oldcurr].left;
		pupdate(node, ptree[curr].right, ptree[oldcurr].right, mid+1, cend);
	}
	ptree[curr].val = ptree[ptree[curr].left].val + ptree[ptree[curr].right].val;
}
int pquery(int s, int e, int curr, int cstart = 0, int cend = 500010)
{
	if (s <= cstart && cend <= e) return ptree[curr].val;
	int mid = (cstart+cend)/2;
	if (e <= mid) return pquery(s, e, ptree[curr].left, cstart, mid);
	else if (s > mid) return pquery(s, e, ptree[curr].right, mid+1, cend);
	else return pquery(s, e, ptree[curr].left, cstart, mid) + pquery(s, e, ptree[curr].right, mid+1, cend);
}
struct otreenode
{
	int left, right, val, last, lazy; // val = last in its subtree;
};
otreenode otree[20000000];
int upto2, n;
int roots[500010];
void push(int curr, int cstart, int mid, int cend)
{
	if (!otree[curr].left) otree[curr].left = ++upto2;
	if (!otree[curr].right) otree[curr].right = ++upto2;
	if (!otree[curr].lazy) return;
	int l = otree[curr].left;
	int r = otree[curr].right;
	otree[l].last = otree[r].last = otree[l].lazy = otree[r].lazy = otree[curr].lazy;
	int a = pquery(cstart, mid, roots[otree[curr].lazy]);
	int b = pquery(mid+1, cend, roots[otree[curr].lazy]);
//	printf("%d %d %d a %d b %d\n", cstart, mid, cend, a, b);
	otree[l].val = a;
	otree[r].val = b;
	otree[curr].lazy = 0;
}
void oupdate(int s, int e, int val, int curr, int cstart = 0, int cend = 500010)
{
	if (s <= cstart && cend <= e)
	{
//		printf("updating %d %d %d\n", cstart, cend, val);
		otree[curr].last = otree[curr].lazy = val;
		int a = pquery(cstart, cend, roots[val]);
		otree[curr].val = a;
//		printf("a %d\n", a);
		return;
	}
	int mid = (cstart+cend)/2;
	push(curr, cstart, mid, cend);
	if (e <= mid) oupdate(s, e, val, otree[curr].left, cstart, mid);
	else if (s > mid) oupdate(s, e, val, otree[curr].right, mid+1, cend);
	else
	{
		oupdate(s, e, val, otree[curr].left, cstart, mid);
		oupdate(s, e, val, otree[curr].right, mid+1, cend);
	}
	otree[curr].val = otree[otree[curr].left].val + otree[otree[curr].right].val;
	otree[curr].last = otree[otree[curr].right].last;
}
int treewalkfindfirstbelow(int val, int curr, int cstart = 0, int cend = 500010)
{
	if (cstart == cend) return cstart;
	int mid = (cstart+cend)/2;
	push(curr, cstart, mid, cend);
	if (otree[otree[curr].left].last <= val) return treewalkfindfirstbelow(val, otree[curr].left, cstart, mid);
	else return treewalkfindfirstbelow(val, otree[curr].right, mid+1, cend);
}
int ROOT;
int othertreewalk(int amreq, int e, int curr, int cstart = 0, int cend = 500010, int amtoside = 0)
{
	if (cstart == cend)
	{
		amtoside += otree[curr].val;
		int hei = otree[curr].last;
		//printf("%d %d %d - %d %d\n", amreq, e, cstart, pquery(cstart, e, roots[n]), amtoside);
		if (pquery(cstart, e, roots[n])-amtoside < amreq)
		{
			// Impossible
			// what a shame
			return 0;
		}
		int S = hei;
		int E = n;
		while (S != E)
		{
			int mid = (S+E)/2;
			if (pquery(cstart, e, roots[mid])-amtoside < amreq) S = mid+1;
			else E = mid;
		}
	//	printf("%d %d %d - %d, %d %d\n", cstart, e, S, amreq, pquery(cstart, e, roots[S]), amtoside);
		oupdate(cstart, e, S, ROOT);
		return 1;
	}
	int mid = (cstart+cend)/2;
	push(curr, cstart, mid, cend);
	// consider last in left subtree
	int h = otree[otree[curr].left].last;
	int am = -1;
	if (mid+1 <= e) am = pquery(mid+1, e, roots[h]) - otree[otree[curr].right].val - amtoside;
//	printf("%d %d am %d - %d mid+1, e, %d %d - query %d right val %d, amtoside %d\n", cstart, cend, am, h, mid+1, e, am+otree[otree[curr].right].val + amtoside, otree[otree[curr].right].val, amtoside);
	if (am < amreq) // have to go to left
	{
		amtoside += otree[otree[curr].right].val;
		return othertreewalk(amreq, e, otree[curr].left, cstart, mid, amtoside);
	}
	else
	{
		return othertreewalk(amreq, e, otree[curr].right, mid+1, cend, amtoside);
	}
}
int lastA[500010];
int lastB[500010];
int x[500010], y[500010];
void init(int N, int A[], int B[]) {
	n = N;
	fill_n(lastA, 500010, 0);
	fill_n(lastB, 500010, 0);
	vector<pair<int, int> > sortedbyA;
	for (int i = 0; i < n; i++)
	{
		sortedbyA.emplace_back(A[i], i);
	}
	sort(sortedbyA.begin(), sortedbyA.end());
	for (int i = 0; i < n; i++)
	{
		if (i == n-1)
		{
			for (int j = sortedbyA[i].first; j <= N; j++) lastA[j] = i+1;
		}
		else if (sortedbyA[i].first != sortedbyA[i+1].first)
		{
			for (int j = sortedbyA[i].first; j < sortedbyA[i+1].first; j++)
			{
				lastA[j] = i+1;
			}
		}
		x[sortedbyA[i].second] = i+1;
	}
	sortedbyA.clear();
	for (int i = 0; i < n; i++)
	{
		sortedbyA.emplace_back(B[i], i);
	}
	sort(sortedbyA.begin(), sortedbyA.end());
	for (int i = 0; i < n; i++)
	{
		if (i == n-1)
		{
			for (int j = sortedbyA[i].first; j <= N; j++) lastB[j] = i+1;
		}
		else if (sortedbyA[i].first != sortedbyA[i+1].first)
		{
			for (int j = sortedbyA[i].first; j < sortedbyA[i+1].first; j++)
			{
				lastB[j] = i+1;
			}
		}
		y[sortedbyA[i].second] = i+1;
	}
	sortedbyA.clear();
	for (int i = 0; i < n; i++)
	{
	//	printf("%d %d\n", x[i], y[i]);
		sortedbyA.emplace_back(y[i], x[i]);
	}
	sort(sortedbyA.begin(), sortedbyA.end());
	for (auto a : sortedbyA)
	{
	//	assert(!roots[a.first]);
		roots[a.first] = ++upto;
	//	printf("at %d - updating %d\n", a.first, a.second);
		pupdate(a.second, roots[a.first], roots[a.first-1]);
	//	printf("%d\n", pquery(0, n, roots[a.first]));
	}
}

int can(int m, int k[]) {
	sort(k, k+m);
	int r = ++upto2;
	ROOT = r;
	for (int i = 0; i < m; i++)
	{
		int a = lastA[k[i]];
		int b = lastB[k[i]-1];
		int s = treewalkfindfirstbelow(b, r);
//		printf("%d\n", s);
		if (s <= n) oupdate(s, n, b, r);
		int res = othertreewalk(k[i], a, r);
		if (!res) return 0;
	}
	return 1;
}

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