Submission #1083922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083922		fv3	Comparing Plants (IOI20_plants)	C++17	27 / 100	384 ms	15864 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;

int K, N;
vector<int> R;

struct node
{
	int mn;
	int mn_index;
	int z;
};
const node empty_node = {INF, 0, 0};
node merge(const node a, const node b)
{
	if (a.mn <= b.mn)
		return {a.mn, a.mn_index, 0};
	return {b.mn, b.mn_index, 0};
}

int nt;
vector<node> st;

void update(int k)
{
	st[k*2].mn -= st[k].z;
	st[k*2|1].mn -= st[k].z;

	st[k*2].z += st[k].z;
	st[k*2|1].z += st[k].z;

	st[k].z = 0;
}

node get_range(int l, int r, int k, int tl, int tr)
{
	if (tr < l || tl > r) return empty_node;
	if (tl >= l && tr <= r) return st[k];

	update(k);

	int c = (tl + tr) / 2;
	return merge(get_range(l, r, k*2, tl, c), get_range(l, r, k*2|1, c+1, tr));
}

void subtract_range(int l, int r, int k, int tl, int tr)
{
	if (tr < l || tl > r) return;
	if (tl >= l && tr <= r)
	{
		st[k].z++;
		st[k].mn--;
		return;
	}

	update(k);

	int c = (tl + tr) / 2;
	subtract_range(l, r, k*2, tl, c);
	subtract_range(l, r, k*2|1, c+1, tr);
	st[k] = merge(st[k*2], st[k*2|1]);
}

void rem(int i, int k, int tl, int tr)
{
	if (tl == tr && tl == i)
	{
		st[k].mn = INF;
		st[k].z = 0;
		return;
	}

	update(k);

	int c = (tl + tr) / 2;
	if (i <= c)	rem(i, k*2, tl, c);
	else		rem(i, k*2|1, c+1, tr);

	st[k] = merge(st[k*2], st[k*2|1]);
}

bool check(int s)
{
	if (s == 0)
		s = N;

	node n;
	if (s - K + 1 < 0)
		n = merge(get_range(0, s-1, 1, 0, nt-1), get_range(N-(K-s)+1, N-1, 1, 0, nt-1));
	else
		n = get_range(s-K+1, s-1, 1, 0, nt-1);

	if (n.mn == 0)
		return false;
	
	if (s - K + 1 < 0)
	{
		subtract_range(0, s-1, 1, 0, nt-1);
		subtract_range(N-(K-s)+1, N-1, 1, 0, nt-1);
	}
	else
	{
		subtract_range(s-K+1, s-1, 1, 0, nt-1);
	}

	return true;
}

vector<int> H;
void init(int k, vector<int> r) 
{
	R = r; K = k;
	N = (int)r.size();

	nt = 1;
	while (nt < N) nt <<= 1;
	st = vector<node>(2*nt, empty_node);

	for (int i = 0; i < N; i++)
		st[nt + i] = {R[i], i, 0};

	for (int i = nt-1; i >= 1; i--)
		st[i] = merge(st[i*2], st[i*2|1]);

	// Find ordering in O(NlogN)
	H = vector<int>(N);
	for (int i = 0; i < N; i++)
	{
		int mn = st[1].mn_index;

		if (!check(mn))
		{
			node n = get_range(N-(K-mn)+1, N-1, 1, 0, nt-1);
			mn = n.mn_index;
			check(mn);
		}

		H[mn] = N - i;
		rem(mn, 1, 0, nt-1);
	}
}

int compare_plants(int x, int y) 
{
	if (H[x] > H[y])
		return 1;
	return -1;
}

#ifdef TEST
#include "grader.cpp"
#endif

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25