oj.uz

Submission #584832

# Submission time Handle Problem Language Result Execution time Memory
584832 2022-06-28T04:39:44 Z AngusRitossa Teams (IOI15_teams) C++14
77 / 100
 4000 ms 500048 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4152 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 2 ms 4308 KB Output is correct
7 Correct 7 ms 4436 KB Output is correct
8 Correct 5 ms 4460 KB Output is correct
9 Correct 3 ms 4308 KB Output is correct
10 Correct 6 ms 4436 KB Output is correct
11 Correct 4 ms 4180 KB Output is correct
12 Correct 14 ms 4436 KB Output is correct
13 Correct 7 ms 4416 KB Output is correct
14 Correct 6 ms 4436 KB Output is correct
15 Correct 3 ms 4408 KB Output is correct
16 Correct 4 ms 4308 KB Output is correct
17 Correct 5 ms 4308 KB Output is correct
18 Correct 3 ms 4308 KB Output is correct
19 Correct 5 ms 4336 KB Output is correct
20 Correct 4 ms 4356 KB Output is correct
21 Correct 3 ms 4308 KB Output is correct
22 Correct 4 ms 4280 KB Output is correct
23 Correct 3 ms 4308 KB Output is correct
24 Correct 3 ms 4308 KB Output is correct
25 Correct 3 ms 4308 KB Output is correct
26 Correct 4 ms 4308 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 31632 KB Output is correct
2 Correct 83 ms 31620 KB Output is correct
3 Correct 82 ms 31664 KB Output is correct
4 Correct 88 ms 31860 KB Output is correct
5 Correct 77 ms 31288 KB Output is correct
6 Correct 73 ms 31232 KB Output is correct
7 Correct 63 ms 31308 KB Output is correct
8 Correct 65 ms 31312 KB Output is correct
9 Correct 246 ms 31300 KB Output is correct
10 Correct 158 ms 31044 KB Output is correct
11 Correct 60 ms 31164 KB Output is correct
12 Correct 52 ms 31196 KB Output is correct
13 Correct 68 ms 31476 KB Output is correct
14 Correct 77 ms 31424 KB Output is correct
15 Correct 70 ms 31560 KB Output is correct
16 Correct 66 ms 31672 KB Output is correct
17 Correct 67 ms 31540 KB Output is correct
18 Correct 69 ms 31624 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 31876 KB Output is correct
2 Correct 78 ms 31936 KB Output is correct
3 Correct 1197 ms 200128 KB Output is correct
4 Correct 76 ms 31804 KB Output is correct
5 Correct 909 ms 59836 KB Output is correct
6 Correct 795 ms 57016 KB Output is correct
7 Correct 69 ms 31552 KB Output is correct
8 Correct 606 ms 50544 KB Output is correct
9 Correct 210 ms 31292 KB Output is correct
10 Correct 609 ms 31168 KB Output is correct
11 Correct 726 ms 31716 KB Output is correct
12 Correct 928 ms 52496 KB Output is correct
13 Correct 1366 ms 83092 KB Output is correct
14 Correct 1274 ms 152180 KB Output is correct
15 Correct 472 ms 56652 KB Output is correct
16 Correct 498 ms 57816 KB Output is correct
17 Correct 488 ms 51072 KB Output is correct
18 Correct 524 ms 47336 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 141888 KB Output is correct
2 Correct 445 ms 141900 KB Output is correct
3 Correct 3318 ms 500048 KB Output is correct
4 Correct 473 ms 141844 KB Output is correct
5 Correct 2589 ms 203144 KB Output is correct
6 Correct 2310 ms 196544 KB Output is correct
7 Correct 335 ms 139184 KB Output is correct
8 Correct 1933 ms 184740 KB Output is correct
9 Correct 1457 ms 139708 KB Output is correct
10 Correct 1875 ms 137900 KB Output is correct
11 Correct 2212 ms 143200 KB Output is correct
12 Correct 2948 ms 197984 KB Output is correct
13 Execution timed out 4054 ms 252492 KB Time limit exceeded
14 Halted 0 ms 0 KB -