oj.uz

답안 #1050764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1050764 2024-08-09T14:03:25 Z aykhn 식물 비교 (IOI20_plants) C++17
100 / 100
 780 ms 175412 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 (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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 45656 KB Output is correct
2 Correct 4 ms 49756 KB Output is correct
3 Correct 3 ms 49756 KB Output is correct
4 Correct 4 ms 49756 KB Output is correct
5 Correct 4 ms 49628 KB Output is correct
6 Correct 37 ms 53236 KB Output is correct
7 Correct 85 ms 62548 KB Output is correct
8 Correct 359 ms 164600 KB Output is correct
9 Correct 396 ms 164900 KB Output is correct
10 Correct 407 ms 164680 KB Output is correct
11 Correct 432 ms 163412 KB Output is correct
12 Correct 453 ms 163924 KB Output is correct
13 Correct 405 ms 153652 KB Output is correct
14 Correct 479 ms 175412 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 49752 KB Output is correct
2 Correct 4 ms 49752 KB Output is correct
3 Correct 4 ms 49756 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 50268 KB Output is correct
7 Correct 67 ms 54536 KB Output is correct
8 Correct 5 ms 49756 KB Output is correct
9 Correct 6 ms 52316 KB Output is correct
10 Correct 67 ms 54612 KB Output is correct
11 Correct 70 ms 54352 KB Output is correct
12 Correct 60 ms 54864 KB Output is correct
13 Correct 69 ms 54584 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 49752 KB Output is correct
2 Correct 4 ms 49752 KB Output is correct
3 Correct 4 ms 49756 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 50268 KB Output is correct
7 Correct 67 ms 54536 KB Output is correct
8 Correct 5 ms 49756 KB Output is correct
9 Correct 6 ms 52316 KB Output is correct
10 Correct 67 ms 54612 KB Output is correct
11 Correct 70 ms 54352 KB Output is correct
12 Correct 60 ms 54864 KB Output is correct
13 Correct 69 ms 54584 KB Output is correct
14 Correct 109 ms 61524 KB Output is correct
15 Correct 737 ms 160524 KB Output is correct
16 Correct 114 ms 61460 KB Output is correct
17 Correct 747 ms 160568 KB Output is correct
18 Correct 517 ms 159316 KB Output is correct
19 Correct 592 ms 163668 KB Output is correct
20 Correct 780 ms 165412 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 49752 KB Output is correct
2 Correct 4 ms 49756 KB Output is correct
3 Correct 59 ms 53228 KB Output is correct
4 Correct 471 ms 159964 KB Output is correct
5 Correct 473 ms 154368 KB Output is correct
6 Correct 506 ms 152912 KB Output is correct
7 Correct 521 ms 153428 KB Output is correct
8 Correct 680 ms 158468 KB Output is correct
9 Correct 462 ms 153428 KB Output is correct
10 Correct 454 ms 155140 KB Output is correct
11 Correct 398 ms 151876 KB Output is correct
12 Correct 512 ms 174932 KB Output is correct
13 Correct 515 ms 156612 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 51804 KB Output is correct
2 Correct 4 ms 49660 KB Output is correct
3 Correct 4 ms 51804 KB Output is correct
4 Correct 4 ms 49752 KB Output is correct
5 Correct 4 ms 49756 KB Output is correct
6 Correct 5 ms 49756 KB Output is correct
7 Correct 14 ms 50776 KB Output is correct
8 Correct 12 ms 50776 KB Output is correct
9 Correct 13 ms 50780 KB Output is correct
10 Correct 13 ms 50792 KB Output is correct
11 Correct 13 ms 50804 KB Output is correct
12 Correct 14 ms 50780 KB Output is correct
13 Correct 15 ms 50780 KB Output is correct

Subtask #6
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 51804 KB Output is correct
2 Correct 4 ms 49752 KB Output is correct
3 Correct 4 ms 49752 KB Output is correct
4 Correct 4 ms 49604 KB Output is correct
5 Correct 5 ms 50012 KB Output is correct
6 Correct 405 ms 154452 KB Output is correct
7 Correct 419 ms 154512 KB Output is correct
8 Correct 512 ms 155088 KB Output is correct
9 Correct 601 ms 160084 KB Output is correct
10 Correct 363 ms 154768 KB Output is correct
11 Correct 404 ms 159300 KB Output is correct
12 Correct 348 ms 161108 KB Output is correct
13 Correct 448 ms 155728 KB Output is correct
14 Correct 456 ms 154452 KB Output is correct
15 Correct 485 ms 154964 KB Output is correct
16 Correct 377 ms 158004 KB Output is correct
17 Correct 403 ms 154524 KB Output is correct

Subtask #7
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 45656 KB Output is correct
2 Correct 4 ms 49756 KB Output is correct
3 Correct 3 ms 49756 KB Output is correct
4 Correct 4 ms 49756 KB Output is correct
5 Correct 4 ms 49628 KB Output is correct
6 Correct 37 ms 53236 KB Output is correct
7 Correct 85 ms 62548 KB Output is correct
8 Correct 359 ms 164600 KB Output is correct
9 Correct 396 ms 164900 KB Output is correct
10 Correct 407 ms 164680 KB Output is correct
11 Correct 432 ms 163412 KB Output is correct
12 Correct 453 ms 163924 KB Output is correct
13 Correct 405 ms 153652 KB Output is correct
14 Correct 479 ms 175412 KB Output is correct
15 Correct 4 ms 49752 KB Output is correct
16 Correct 4 ms 49752 KB Output is correct
17 Correct 4 ms 49756 KB Output is correct
18 Correct 4 ms 49756 KB Output is correct
19 Correct 4 ms 49756 KB Output is correct
20 Correct 6 ms 50268 KB Output is correct
21 Correct 67 ms 54536 KB Output is correct
22 Correct 5 ms 49756 KB Output is correct
23 Correct 6 ms 52316 KB Output is correct
24 Correct 67 ms 54612 KB Output is correct
25 Correct 70 ms 54352 KB Output is correct
26 Correct 60 ms 54864 KB Output is correct
27 Correct 69 ms 54584 KB Output is correct
28 Correct 109 ms 61524 KB Output is correct
29 Correct 737 ms 160524 KB Output is correct
30 Correct 114 ms 61460 KB Output is correct
31 Correct 747 ms 160568 KB Output is correct
32 Correct 517 ms 159316 KB Output is correct
33 Correct 592 ms 163668 KB Output is correct
34 Correct 780 ms 165412 KB Output is correct
35 Correct 4 ms 49752 KB Output is correct
36 Correct 4 ms 49756 KB Output is correct
37 Correct 59 ms 53228 KB Output is correct
38 Correct 471 ms 159964 KB Output is correct
39 Correct 473 ms 154368 KB Output is correct
40 Correct 506 ms 152912 KB Output is correct
41 Correct 521 ms 153428 KB Output is correct
42 Correct 680 ms 158468 KB Output is correct
43 Correct 462 ms 153428 KB Output is correct
44 Correct 454 ms 155140 KB Output is correct
45 Correct 398 ms 151876 KB Output is correct
46 Correct 512 ms 174932 KB Output is correct
47 Correct 515 ms 156612 KB Output is correct
48 Correct 4 ms 51804 KB Output is correct
49 Correct 4 ms 49660 KB Output is correct
50 Correct 4 ms 51804 KB Output is correct
51 Correct 4 ms 49752 KB Output is correct
52 Correct 4 ms 49756 KB Output is correct
53 Correct 5 ms 49756 KB Output is correct
54 Correct 14 ms 50776 KB Output is correct
55 Correct 12 ms 50776 KB Output is correct
56 Correct 13 ms 50780 KB Output is correct
57 Correct 13 ms 50792 KB Output is correct
58 Correct 13 ms 50804 KB Output is correct
59 Correct 14 ms 50780 KB Output is correct
60 Correct 15 ms 50780 KB Output is correct
61 Correct 56 ms 54352 KB Output is correct
62 Correct 87 ms 62180 KB Output is correct
63 Correct 394 ms 156756 KB Output is correct
64 Correct 489 ms 154964 KB Output is correct
65 Correct 494 ms 154708 KB Output is correct
66 Correct 548 ms 155456 KB Output is correct
67 Correct 721 ms 160740 KB Output is correct
68 Correct 428 ms 155216 KB Output is correct
69 Correct 431 ms 159900 KB Output is correct
70 Correct 470 ms 161868 KB Output is correct
71 Correct 516 ms 156240 KB Output is correct
72 Correct 503 ms 154764 KB Output is correct
73 Correct 582 ms 155472 KB Output is correct
74 Correct 418 ms 155984 KB Output is correct
75 Correct 452 ms 155220 KB Output is correct