oj.uz

Submission #1083922

# Submission time Handle Problem Language Result Execution time Memory
1083922 2024-09-04T14:15:33 Z fv3 Comparing Plants (IOI20_plants) C++17
27 / 100
 384 ms 15864 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, 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.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 Incorrect 0 ms 360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 38 ms 5284 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 40 ms 5292 KB Output is correct
11 Correct 35 ms 5208 KB Output is correct
12 Correct 35 ms 5460 KB Output is correct
13 Correct 39 ms 5352 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 38 ms 5284 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 40 ms 5292 KB Output is correct
11 Correct 35 ms 5208 KB Output is correct
12 Correct 35 ms 5460 KB Output is correct
13 Correct 39 ms 5352 KB Output is correct
14 Correct 61 ms 6424 KB Output is correct
15 Correct 384 ms 15788 KB Output is correct
16 Correct 66 ms 6480 KB Output is correct
17 Correct 377 ms 15700 KB Output is correct
18 Correct 258 ms 15320 KB Output is correct
19 Correct 250 ms 15864 KB Output is correct
20 Correct 348 ms 15696 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 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 #7
0 / 25.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 Incorrect 0 ms 360 KB Output isn't correct
5 Halted 0 ms 0 KB -