oj.uz

Submission #1083889

# Submission time Handle Problem Language Result Execution time Memory
1083889 2024-09-04T12:43:23 Z fv3 Comparing Plants (IOI20_plants) C++17
0 / 100
 37 ms 4932 KB 
#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, min(a.mn_index, b.mn_index)};
	if (a.mn < b.mn)
		return a;
	else
		return b;
}

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;
		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)
{
	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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 37 ms 4932 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -