Submission #1050576

# Submission time Handle Problem Language Result Execution time Memory
1050576 2024-08-09T11:28:01 Z aykhn Comparing Plants (IOI20_plants) C++17
30 / 100
676 ms 96612 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;
	long long d = (y - x + n) % n;
	long long res = 0;
	for (int 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 (int 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 (check(x, y)) return -1;
	if (check(y, x)) return 1;
	return 0;
	// return (a[x] > a[y] ? 1 : -1);
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 35420 KB Output is correct
2 Correct 3 ms 33372 KB Output is correct
3 Correct 2 ms 33372 KB Output is correct
4 Correct 3 ms 35308 KB Output is correct
5 Correct 2 ms 33372 KB Output is correct
6 Correct 36 ms 34044 KB Output is correct
7 Correct 77 ms 40332 KB Output is correct
8 Correct 322 ms 87432 KB Output is correct
9 Correct 348 ms 87636 KB Output is correct
10 Correct 361 ms 87380 KB Output is correct
11 Correct 397 ms 86528 KB Output is correct
12 Correct 386 ms 86864 KB Output is correct
13 Correct 340 ms 77820 KB Output is correct
14 Correct 405 ms 96612 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 35420 KB Output is correct
2 Correct 2 ms 31196 KB Output is correct
3 Correct 2 ms 31364 KB Output is correct
4 Correct 2 ms 31212 KB Output is correct
5 Correct 2 ms 31324 KB Output is correct
6 Correct 5 ms 31580 KB Output is correct
7 Correct 62 ms 37152 KB Output is correct
8 Correct 4 ms 31320 KB Output is correct
9 Correct 5 ms 33628 KB Output is correct
10 Correct 62 ms 39136 KB Output is correct
11 Correct 64 ms 35156 KB Output is correct
12 Correct 69 ms 35504 KB Output is correct
13 Correct 63 ms 37240 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 35420 KB Output is correct
2 Correct 2 ms 31196 KB Output is correct
3 Correct 2 ms 31364 KB Output is correct
4 Correct 2 ms 31212 KB Output is correct
5 Correct 2 ms 31324 KB Output is correct
6 Correct 5 ms 31580 KB Output is correct
7 Correct 62 ms 37152 KB Output is correct
8 Correct 4 ms 31320 KB Output is correct
9 Correct 5 ms 33628 KB Output is correct
10 Correct 62 ms 39136 KB Output is correct
11 Correct 64 ms 35156 KB Output is correct
12 Correct 69 ms 35504 KB Output is correct
13 Correct 63 ms 37240 KB Output is correct
14 Correct 103 ms 40504 KB Output is correct
15 Incorrect 676 ms 84172 KB Output isn't correct
16 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 31320 KB Output is correct
2 Correct 3 ms 33368 KB Output is correct
3 Correct 53 ms 36600 KB Output is correct
4 Correct 405 ms 84684 KB Output is correct
5 Correct 406 ms 79908 KB Output is correct
6 Correct 452 ms 78764 KB Output is correct
7 Correct 475 ms 78836 KB Output is correct
8 Incorrect 616 ms 82768 KB Output isn't correct
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 33372 KB Output is correct
2 Correct 2 ms 33372 KB Output is correct
3 Correct 2 ms 31180 KB Output is correct
4 Correct 2 ms 33372 KB Output is correct
5 Correct 2 ms 31324 KB Output is correct
6 Correct 3 ms 31276 KB Output is correct
7 Correct 12 ms 31952 KB Output is correct
8 Correct 11 ms 32092 KB Output is correct
9 Correct 12 ms 33884 KB Output is correct
10 Correct 11 ms 34020 KB Output is correct
11 Correct 11 ms 31836 KB Output is correct
12 Correct 12 ms 33884 KB Output is correct
13 Correct 12 ms 33884 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 35420 KB Output is correct
2 Correct 2 ms 31324 KB Output is correct
3 Correct 2 ms 33368 KB Output is correct
4 Correct 3 ms 33372 KB Output is correct
5 Correct 4 ms 31588 KB Output is correct
6 Correct 388 ms 78640 KB Output is correct
7 Correct 385 ms 78388 KB Output is correct
8 Correct 472 ms 78880 KB Output is correct
9 Incorrect 607 ms 82772 KB Output isn't correct
10 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 35420 KB Output is correct
2 Correct 3 ms 33372 KB Output is correct
3 Correct 2 ms 33372 KB Output is correct
4 Correct 3 ms 35308 KB Output is correct
5 Correct 2 ms 33372 KB Output is correct
6 Correct 36 ms 34044 KB Output is correct
7 Correct 77 ms 40332 KB Output is correct
8 Correct 322 ms 87432 KB Output is correct
9 Correct 348 ms 87636 KB Output is correct
10 Correct 361 ms 87380 KB Output is correct
11 Correct 397 ms 86528 KB Output is correct
12 Correct 386 ms 86864 KB Output is correct
13 Correct 340 ms 77820 KB Output is correct
14 Correct 405 ms 96612 KB Output is correct
15 Correct 3 ms 35420 KB Output is correct
16 Correct 2 ms 31196 KB Output is correct
17 Correct 2 ms 31364 KB Output is correct
18 Correct 2 ms 31212 KB Output is correct
19 Correct 2 ms 31324 KB Output is correct
20 Correct 5 ms 31580 KB Output is correct
21 Correct 62 ms 37152 KB Output is correct
22 Correct 4 ms 31320 KB Output is correct
23 Correct 5 ms 33628 KB Output is correct
24 Correct 62 ms 39136 KB Output is correct
25 Correct 64 ms 35156 KB Output is correct
26 Correct 69 ms 35504 KB Output is correct
27 Correct 63 ms 37240 KB Output is correct
28 Correct 103 ms 40504 KB Output is correct
29 Incorrect 676 ms 84172 KB Output isn't correct
30 Halted 0 ms 0 KB -