oj.uz

Submission #1050762

# Submission time Handle Problem Language Result Execution time Memory
1050762 2024-08-09T14:01:07 Z aykhn Comparing Plants (IOI20_plants) C++17
44 / 100
 589 ms 176388 KB 
#include "plants.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const long long MXN = 2e5 + 5;
const long long LOG = 20;
 
#define inf 0x3F3F3F3F
 
long long n;
array<long long, 2> p[2][LOG][MXN];
long long rr[MXN], f[MXN];
long long cnt[MXN];
array<long long, 2> st[MXN << 2];
long long lz[MXN << 2];
 
void build(long long l, long long r, long long x)
{
	if (l == r)
	{
		st[x] = {cnt[l] - rr[l], l};
		return;
	}
	long long 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(long long l, long long r, long long 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(long long l, long long r, long long x, long long lx, long long rx, long long 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;
	}
	long long 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<long long> idx;
set<array<long long, 2>> dif;
 
void ins(long long 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(long long 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 (long long i = 1; i <= (n * 4); i++) st[i] = {inf, -1};
	for (long long i = 0; i < n; i++) rr[i] = r[i];
	for (long long i = 0; i < n; i++) cnt[i] = k - 1;
	build(0, n - 1, 1);
	while (1)
	{
		array<long long, 2> x = st[1];
		if (!x[0]) 
		{
			ins(x[1]);
			upd(0, n - 1, 1, x[1], x[1], inf);
		}
		else break;
	}
	long long cur = 0;
	while (!idx.empty())
	{
		long long ind = (*dif.rbegin())[1];
		ers(ind);
		f[ind] = ++cur;
		if (ind - 1 >= 0) upd(0, n - 1, 1, max(ind - k + 1, 0LL), ind - 1, -1);
		if (ind - k + 1 < 0) upd(0, n - 1, 1, (ind - k + 1 + n) % n, n - 1, -1);
		// for (long long 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 (long long i = (idx[ind] + 1) % n; i != (idx[ind] + k) % n; i = (i + 1) % n)
		// {
		// 	if (!f[i]) adj[idx[ind]].push_back(i);
		// }
		// for (long long 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<long long, 2> x = st[1];
			if (!x[0]) 
			{
				ins(x[1]);
				upd(0, n - 1, 1, x[1], x[1], inf);
			}
			else break;
		}
	}
	set<array<long long, 2>> s;
	for (long long i = 0; i < k; i++) s.insert({f[i], i});
	for (long long 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 (long long i = n - k; i < n; i++) s.insert({f[i], i});
	for (long long 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 (long long i = 0; i < n; i++)
	// {
	// 	cout << f[i] << ' ';
	// }
	// cout << '\n';
	// for (long long i = 0; i < n; i++)
	// {
	// 	cout << p[0][0][i][0] << ' ';
	// }
	// cout << '\n';
	// for (long long i = 0; i < n; i++)
	// {
	// 	cout << p[1][0][i][0] << ' ';
	// }
	// cout << '\n';
	for (long long j = 0; j < 2; j++)
	{
		for (long long i = 1; i < LOG; i++)
		{
			for (long long k = 0; k <= n; k++)
			{
				long long 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]};
			}
		}
	}
}
 
long long check(long long x, long long y)
{
	long long x1 = x;
	long long d = (y - x + n) % n;
	long long res = 0;
	for (long long i = LOG - 1; i >= 0; i--)
	{
		if (f[p[0][i][x][0]] <= f[y]) 
		{
			res += 1LL * 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 (long long i = LOG - 1; i >= 0; i--)
	{
		if (f[p[1][i][x][0]] <= f[y]) 
		{
			res += 1LL * 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 (f[x] < f[y]) return -1;
  	if (f[y] < f[x]) return 1;
  	return 0;
	// return (a[x] > a[y] ? 1 : -1);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 49752 KB Output is correct
2 Correct 5 ms 51804 KB Output is correct
3 Correct 4 ms 49756 KB Output is correct
4 Incorrect 4 ms 49756 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 3 ms 49616 KB Output is correct
2 Correct 4 ms 49756 KB Output is correct
3 Correct 4 ms 51804 KB Output is correct
4 Correct 4 ms 49756 KB Output is correct
5 Correct 4 ms 49756 KB Output is correct
6 Correct 6 ms 52356 KB Output is correct
7 Correct 39 ms 55892 KB Output is correct
8 Correct 4 ms 49752 KB Output is correct
9 Correct 6 ms 52316 KB Output is correct
10 Correct 38 ms 56012 KB Output is correct
11 Correct 34 ms 57584 KB Output is correct
12 Correct 38 ms 56144 KB Output is correct
13 Correct 38 ms 55888 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 49616 KB Output is correct
2 Correct 4 ms 49756 KB Output is correct
3 Correct 4 ms 51804 KB Output is correct
4 Correct 4 ms 49756 KB Output is correct
5 Correct 4 ms 49756 KB Output is correct
6 Correct 6 ms 52356 KB Output is correct
7 Correct 39 ms 55892 KB Output is correct
8 Correct 4 ms 49752 KB Output is correct
9 Correct 6 ms 52316 KB Output is correct
10 Correct 38 ms 56012 KB Output is correct
11 Correct 34 ms 57584 KB Output is correct
12 Correct 38 ms 56144 KB Output is correct
13 Correct 38 ms 55888 KB Output is correct
14 Correct 68 ms 62804 KB Output is correct
15 Correct 589 ms 162672 KB Output is correct
16 Correct 68 ms 62748 KB Output is correct
17 Correct 579 ms 162668 KB Output is correct
18 Correct 320 ms 161056 KB Output is correct
19 Correct 486 ms 165732 KB Output is correct
20 Correct 583 ms 167276 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 49752 KB Output is correct
2 Correct 4 ms 51804 KB Output is correct
3 Correct 35 ms 54452 KB Output is correct
4 Correct 267 ms 161616 KB Output is correct
5 Correct 323 ms 156244 KB Output is correct
6 Correct 379 ms 154724 KB Output is correct
7 Correct 453 ms 155468 KB Output is correct
8 Correct 555 ms 160576 KB Output is correct
9 Correct 263 ms 155084 KB Output is correct
10 Correct 325 ms 156800 KB Output is correct
11 Correct 166 ms 153544 KB Output is correct
12 Correct 418 ms 176388 KB Output is correct
13 Correct 299 ms 158544 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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