oj.uz

Submission #1050574

# Submission time Handle Problem Language Result Execution time Memory
1050574 2024-08-09T11:25:50 Z aykhn Comparing Plants (IOI20_plants) C++17
30 / 100
 747 ms 99668 KB 
#include "plants.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MXN = 2e5 + 5;
const int LOG = 20;

#define inf 0x3F3F3F3F
 
int n;
array<int, 2> p[2][LOG][MXN];
int rr[MXN], f[MXN];
int cnt[MXN];
array<int, 2> st[MXN << 2];
int lz[MXN << 2];

void build(int l, int r, int x)
{
	if (l == r)
	{
		st[x] = {cnt[l] - rr[l], l};
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, 2*x);
	build(mid + 1, r, 2*x + 1);
	st[x] = min(st[2*x], st[2*x + 1]);
}
void relax(int l, int r, int x)
{
	if (!lz[x]) return;
	st[x][0] += lz[x];
	if (l == r)
	{
		lz[x] = 0;
		return;
	}
	lz[2*x] += lz[x], lz[2*x + 1] += lz[x];
	lz[x] = 0;
}
void upd(int l, int r, int x, int lx, int rx, int val)
{
	if (lx > rx) return;
	relax(l, r, x);
	if (l > rx || r < lx) return;
	if (l >= lx && r <= rx)
	{
		lz[x] += val;
		relax(l, r, x);
		return;
	}
	int mid = (l + r) >> 1;
	upd(l, mid, 2*x, lx, rx, val);
	upd(mid + 1, r, 2*x + 1, lx, rx, val);
	st[x] = min(st[2*x], st[2*x + 1]);
}

set<int> idx;
set<array<int, 2>> dif;

void ins(int x)
{
	idx.insert(x);
	if (idx.size() == 1)
	{
		dif.insert({0, x});
		return;
	}
	auto it = idx.find(x);
	auto itl = it, itr = it;
	if (it == idx.begin()) itl = prev(idx.end());
	else itl = prev(it);
	if (next(it) == idx.end()) itr = idx.begin();
	else itr = next(it);
	dif.erase({(*itr - *itl + n) % n, *itr});
	dif.insert({(x - *itl + n) % n, x});
	dif.insert({(*itr - x + n) % n, *itr});
}
void ers(int x)
{
	if (idx.size() == 1)
	{
		idx.clear();
		dif.clear();
		return;
	}
	auto it = idx.find(x);
	auto itl = it, itr = it;
	if (it == idx.begin()) itl = prev(idx.end());
	else itl = prev(it);
	if (next(it) == idx.end()) itr = idx.begin();
	else itr = next(it);
	dif.erase({(x - *itl + n) % n, x});
	dif.erase({(*itr - x + n) % n, *itr});
	dif.insert({(*itr - *itl + n) % n, *itr});
	idx.erase(it);
}
// 4 3 2
// 0 1 1 2
// 0 2
// 1 2

 
void init(int k, vector<int> r) 
{
	n = r.size();
	f[n] = inf;
	p[0][0][n] = {n, 0};
	p[1][0][n] = {n, 0};
	for (int i = 1; i <= (n * 4); i++) st[i] = {inf, -1};
	for (int i = 0; i < n; i++) rr[i] = r[i];
	for (int i = 0; i < n; i++) cnt[i] = k - 1;
	build(0, n - 1, 1);
	while (1)
	{
		array<int, 2> x = st[1];
		if (!x[0]) 
		{
			ins(x[1]);
			upd(0, n - 1, 1, x[1], x[1], inf);
		}
		else break;
	}
	int cur = 0;
	while (!idx.empty())
	{
		int ind = (*dif.rbegin())[1];
		ers(ind);
		f[ind] = ++cur;
		if (ind - 1 >= 0) upd(0, n - 1, 1, max(ind - k + 1, 0), ind - 1, -1);
		if (ind - k + 1 < 0) upd(0, n - 1, 1, (ind - k + 1 + n) % n, n - 1, -1);
		// for (int i = (idx[ind] - 1 + n) % n; i != idx[(ind - 1 + sz) % sz]; i = (i - 1 + n) % n)
		// {
		// 	if (!f[i]) adj[idx[ind]].push_back(i);
		// }
		// for (int i = (idx[ind] + 1) % n; i != (idx[ind] + k) % n; i = (i + 1) % n)
		// {
		// 	if (!f[i]) adj[idx[ind]].push_back(i);
		// }
		// for (int i = (idx[ind] - 1 + n) % n; i != (idx[ind] - k + n) % n; i = (i - 1 + n) % n)
		// {
		// 	if (!f[i]) adj[idx[ind]].push_back(i);
		// 	cnt[i]--;
		// }
		// f[idx[ind]] = 1;
		while (1)
		{
			array<int, 2> x = st[1];
			if (!x[0]) 
			{
				ins(x[1]);
				upd(0, n - 1, 1, x[1], x[1], inf);
			}
			else break;
		}
	}
	set<array<int, 2>> s;
	for (int i = 0; i < k; i++) s.insert({f[i], i});
	for (int i = n - 1; i >= 0; i--)
	{
		s.erase({f[(i + k) % n], (i + k) % n});
		auto it = s.lower_bound({f[i], i});
		if (it != s.end()) 
		{
			p[0][0][i] = {(*it)[1], ((*it)[1] - i + n) % n};
		}
		else p[0][0][i] = {n, inf};
		s.insert({f[i], i});
	}
	s.clear();
	for (int i = n - k; i < n; i++) s.insert({f[i], i});
	for (int i = 0; i < n; i++)
	{
		s.erase({f[(i - k + n) % n], (i - k + n) % n});
		auto it = s.lower_bound({f[i], i});
		if (it != s.end()) 
		{
			p[1][0][i] = {(*it)[1], (i - (*it)[1] + n) % n};
		}
		else p[1][0][i] = {n, inf};
		s.insert({f[i], i});
	}
	// for (int i = 0; i < n; i++)
	// {
	// 	cout << f[i] << ' ';
	// }
	// cout << '\n';
	// for (int i = 0; i < n; i++)
	// {
	// 	cout << p[0][0][i][0] << ' ';
	// }
	// cout << '\n';
	// for (int i = 0; i < n; i++)
	// {
	// 	cout << p[1][0][i][0] << ' ';
	// }
	// cout << '\n';
	for (int j = 0; j < 2; j++)
	{
		for (int i = 1; i < LOG; i++)
		{
			for (int k = 0; k <= n; k++)
			{
				int par = p[j][i - 1][k][0];
				p[j][i][k] = {p[j][i - 1][par][0], p[j][i - 1][par][1] + p[j][i - 1][k][1]};
			}
		}
	}
}

int check(int x, int y)
{
	int x1 = x;
	int d = (y - x + n) % n;
	int res = 0;
	for (int i = LOG - 1; i >= 0; i--)
	{
		if (f[p[0][i][x][0]] <= f[y]) 
		{
			res += p[0][i][x][1];
			x = p[0][i][x][0];
		}
	}
	if (f[x] <= f[y] && res >= d) return 1;
	res = 0, x = x1;
	d = (x - y + n) % n;
	for (int i = LOG - 1; i >= 0; i--)
	{
		if (f[p[1][i][x][0]] <= f[y]) 
		{
			res += p[1][i][x][1];
			x = p[1][i][x][0];
		}
	}
	return (f[x] <= f[y] && res >= d);
}

int compare_plants(int x, int y) 
{
	// ? x < y
	if (check(x, y)) return -1;
	if (check(y, x)) return 1;
	return 0;
	// return (a[x] > a[y] ? 1 : -1);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 35420 KB Output is correct
2 Correct 2 ms 35420 KB Output is correct
3 Correct 2 ms 33372 KB Output is correct
4 Correct 3 ms 33372 KB Output is correct
5 Correct 2 ms 33372 KB Output is correct
6 Correct 38 ms 37040 KB Output is correct
7 Correct 78 ms 42576 KB Output is correct
8 Correct 339 ms 90192 KB Output is correct
9 Correct 389 ms 90452 KB Output is correct
10 Correct 355 ms 90448 KB Output is correct
11 Correct 386 ms 89432 KB Output is correct
12 Correct 408 ms 89936 KB Output is correct
13 Correct 316 ms 80928 KB Output is correct
14 Correct 407 ms 99668 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33372 KB Output is correct
2 Correct 2 ms 33252 KB Output is correct
3 Correct 2 ms 27228 KB Output is correct
4 Correct 2 ms 29276 KB Output is correct
5 Correct 3 ms 27324 KB Output is correct
6 Correct 4 ms 27484 KB Output is correct
7 Correct 63 ms 33224 KB Output is correct
8 Correct 3 ms 29272 KB Output is correct
9 Correct 5 ms 33628 KB Output is correct
10 Correct 66 ms 39252 KB Output is correct
11 Correct 71 ms 38896 KB Output is correct
12 Correct 57 ms 41296 KB Output is correct
13 Correct 64 ms 41300 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33372 KB Output is correct
2 Correct 2 ms 33252 KB Output is correct
3 Correct 2 ms 27228 KB Output is correct
4 Correct 2 ms 29276 KB Output is correct
5 Correct 3 ms 27324 KB Output is correct
6 Correct 4 ms 27484 KB Output is correct
7 Correct 63 ms 33224 KB Output is correct
8 Correct 3 ms 29272 KB Output is correct
9 Correct 5 ms 33628 KB Output is correct
10 Correct 66 ms 39252 KB Output is correct
11 Correct 71 ms 38896 KB Output is correct
12 Correct 57 ms 41296 KB Output is correct
13 Correct 64 ms 41300 KB Output is correct
14 Correct 103 ms 42744 KB Output is correct
15 Incorrect 747 ms 87892 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 35416 KB Output is correct
2 Correct 3 ms 35416 KB Output is correct
3 Correct 56 ms 38476 KB Output is correct
4 Correct 395 ms 87380 KB Output is correct
5 Correct 425 ms 82820 KB Output is correct
6 Correct 462 ms 81808 KB Output is correct
7 Correct 470 ms 82260 KB Output is correct
8 Incorrect 663 ms 86352 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 35416 KB Output is correct
2 Correct 2 ms 33216 KB Output is correct
3 Correct 2 ms 27228 KB Output is correct
4 Correct 3 ms 33368 KB Output is correct
5 Correct 3 ms 35308 KB Output is correct
6 Correct 4 ms 35420 KB Output is correct
7 Correct 12 ms 34364 KB Output is correct
8 Correct 12 ms 36444 KB Output is correct
9 Correct 12 ms 34400 KB Output is correct
10 Correct 12 ms 36444 KB Output is correct
11 Correct 12 ms 30300 KB Output is correct
12 Correct 12 ms 36696 KB Output is correct
13 Correct 12 ms 34344 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 35420 KB Output is correct
2 Correct 3 ms 33368 KB Output is correct
3 Correct 3 ms 35420 KB Output is correct
4 Correct 3 ms 33372 KB Output is correct
5 Correct 4 ms 33372 KB Output is correct
6 Correct 426 ms 80848 KB Output is correct
7 Correct 391 ms 80980 KB Output is correct
8 Correct 472 ms 81488 KB Output is correct
9 Incorrect 644 ms 85332 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 35420 KB Output is correct
2 Correct 2 ms 35420 KB Output is correct
3 Correct 2 ms 33372 KB Output is correct
4 Correct 3 ms 33372 KB Output is correct
5 Correct 2 ms 33372 KB Output is correct
6 Correct 38 ms 37040 KB Output is correct
7 Correct 78 ms 42576 KB Output is correct
8 Correct 339 ms 90192 KB Output is correct
9 Correct 389 ms 90452 KB Output is correct
10 Correct 355 ms 90448 KB Output is correct
11 Correct 386 ms 89432 KB Output is correct
12 Correct 408 ms 89936 KB Output is correct
13 Correct 316 ms 80928 KB Output is correct
14 Correct 407 ms 99668 KB Output is correct
15 Correct 3 ms 33372 KB Output is correct
16 Correct 2 ms 33252 KB Output is correct
17 Correct 2 ms 27228 KB Output is correct
18 Correct 2 ms 29276 KB Output is correct
19 Correct 3 ms 27324 KB Output is correct
20 Correct 4 ms 27484 KB Output is correct
21 Correct 63 ms 33224 KB Output is correct
22 Correct 3 ms 29272 KB Output is correct
23 Correct 5 ms 33628 KB Output is correct
24 Correct 66 ms 39252 KB Output is correct
25 Correct 71 ms 38896 KB Output is correct
26 Correct 57 ms 41296 KB Output is correct
27 Correct 64 ms 41300 KB Output is correct
28 Correct 103 ms 42744 KB Output is correct
29 Incorrect 747 ms 87892 KB Output isn't correct
30 Halted 0 ms 0 KB -