oj.uz

Submission #809764

# Submission time Handle Problem Language Result Execution time Memory
809764 2023-08-06T03:27:42 Z LittleCube Comparing Plants (IOI20_plants) C++17
49 / 100
 1270 ms 55752 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define ll long long
using namespace std;

namespace
{
	int n, k, state[800005], order[200005], out[200005], in[200005];
	ll l[200005], r[200005];
}

struct segTree
{
	pll seg[800005];
	ll lazy[800005];

	void init(int i = 1, int L = 0, int R = n - 1)
	{
		seg[i].S = L;
		if (L == R)
			return;
		int mid = (L + R) / 2;
		init(i << 1, L, mid);
		init(i << 1 | 1, mid + 1, R);
	}

	void modify(int mL, int mR, ll val, int i = 1, int L = 0, int R = n - 1)
	{
		if (mL <= L && R <= mR)
		{
			lazy[i] += val;
			seg[i].F += val;
		}
		else if (R < mL || mR < L)
			return;
		else
		{
			int mid = (L + R) / 2;
			lazy[i << 1] += lazy[i];
			lazy[i << 1 | 1] += lazy[i];
			seg[i << 1].F += lazy[i];
			seg[i << 1 | 1].F += lazy[i];
			lazy[i] = 0;
			modify(mL, mR, val, i << 1, L, mid);
			modify(mL, mR, val, i << 1 | 1, mid + 1, R);
			seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
		}
	}

	pll query(int qL, int qR, int i = 1, int L = 0, int R = n - 1)
	{
		if (qL <= L && R <= qR)
			return seg[i];
		else if (R < qL || qR < L)
			return pll(1e9, n + 1);
		else
		{
			int mid = (L + R) / 2;
			lazy[i << 1] += lazy[i];
			lazy[i << 1 | 1] += lazy[i];
			seg[i << 1].F += lazy[i];
			seg[i << 1 | 1].F += lazy[i];
			lazy[i] = 0;
			return min(query(qL, qR, i << 1, L, mid),
					   query(qL, qR, i << 1 | 1, mid + 1, R));
		}
	}
	void safe_modify(int l, int r, ll val)
	{
		if (l <= r)
			modify(l, r, val);
		else
		{
			modify(l, n - 1, val);
			modify(0, r, val);
		}
	}
} seg, zero;

struct changeValseg
{
	ll seg[800005];

	void init(int i = 1, int L = 0, int R = n - 1)
	{
		seg[i] = -1;
		if (L == R)
			return;
		int mid = (L + R) / 2;
		init(i << 1, L, mid);
		init(i << 1 | 1, mid + 1, R);
	}

	void modify(int mL, int mR, ll val, int i = 1, int L = 0, int R = n - 1)
	{
		if (mL <= L && R <= mR)
			seg[i] = val;
		else if (R < mL || mR < L)
			return;
		else
		{
			if (seg[i] != -1)
			{
				seg[i << 1] = seg[i << 1 | 1] = seg[i];
				seg[i] = -1;
			}
			int mid = (L + R) / 2;
			modify(mL, mR, val, i << 1, L, mid);
			modify(mL, mR, val, i << 1 | 1, mid + 1, R);
		}
	}

	ll query(int pos, int i = 1, int L = 0, int R = n - 1)
	{
		if (seg[i] != -1 || L == R)
			return seg[i];
		else
		{
			int mid = (L + R) / 2;
			if (pos <= mid)
				return query(pos, i << 1, L, mid);
			else
				return query(pos, i << 1 | 1, mid + 1, R);
		}
	}

	void safe_modify(int l, int r, ll val)
	{
		if (l <= r)
			modify(l, r, val);
		else
		{
			modify(l, n - 1, val);
			modify(0, r, val);
		}
	}
} open, conceal;

const ll inf = 1e9;

void init(int k, vector<int> r)
{
	n = r.size();
	::k = k;
	seg.init();
	zero.init();
	open.init();
	conceal.init();
	for (int i = 0; i < n; i++)
	{
		r[i] = k - 1 - r[i];
		seg.modify(i, i, r[i]);
		zero.modify(i, i, r[i]);
	}
	for (int it = 1; it <= n; it++)
	{
		{
			auto [v, p] = zero.query(0, n - 1);
			while (v == 0)
			{
				seg.safe_modify((p + 1) % n, (p + k - 1) % n, inf);
				zero.modify(p, p, inf);
				out[p] = open.query(p);
				tie(v, p) = zero.query(0, n - 1);
			}
		}
		int cur = seg.query(0, n - 1).S;
		in[cur] = conceal.query(cur);
		// cerr << cur << "->" << in[cur] << ' ' << out[cur] << '\n';
		seg.modify(cur, cur, inf);
		seg.safe_modify((cur + 1) % n, (cur + k - 1) % n, -inf);
		zero.safe_modify((cur - k + 1 + n) % n, cur, -1);
		seg.safe_modify((cur - k + 1 + n) % n, cur, -1);
		conceal.safe_modify((cur + 1) % n, (cur + k - 1) % n, cur);
		open.safe_modify((cur - k + 1 + n) % n, cur, cur);
		assert(order[cur] == 0);
		order[cur] = it;
	}

	vector<int> ord(n);
	for (int i = 0; i < n; i++)
		ord[order[i] - 1] = i;
	for (int i = 0; i < n; i++)
	{
		int u = ord[i];
		if (in[u] >= 0)
			l[u] = l[in[u]] + (u - in[u] + n) % n;
		else
			l[u] = 0;
		if (out[u] >= 0)
			::r[u] = ::r[out[u]] + (out[u] - u + n) % n;
		else
			::r[u] = 0;
	}
	// for (int i = 0; i < n; i++)
	// 	cerr << in[i] << ' ' << l[i] << ' ' << out[i] << ' ' << ::r[i] << '\n';
}

bool reach(int x, int y)
{
	ll L = y - l[y], R = y + r[y];
	if ((L <= x - n && x - n <= R) ||
		(L <= x && x <= R) ||
		(L <= x + n && x + n <= R))
		return order[y] > order[x];
	L = (L + (ll)n * n) % n;
	R = (R + (ll)n * n) % n;
	if ((L - k < x - n && x - n < L) ||
		(L - k < x && x < L))
			return order[L] > order[x];
	if ((R < x - n && x + n < R + k) ||
		(R < x && x < R + k))
			return order[R] > order[x];
	return 0;
}

int compare_plants(int x, int y)
{
	if (reach(x, y))
		return -1;
	if (reach(y, x))
		return 1;
	return 0;
}

Compilation message

plants.cpp:12:12: warning: '{anonymous}::state' defined but not used [-Wunused-variable]
   12 |  int n, k, state[800005], order[200005], out[200005], in[200005];
      |            ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25300 KB Output is correct
2 Correct 10 ms 25376 KB Output is correct
3 Correct 10 ms 25340 KB Output is correct
4 Correct 10 ms 25344 KB Output is correct
5 Correct 9 ms 25384 KB Output is correct
6 Correct 63 ms 28292 KB Output is correct
7 Correct 102 ms 31132 KB Output is correct
8 Correct 583 ms 54792 KB Output is correct
9 Correct 603 ms 54804 KB Output is correct
10 Correct 593 ms 54800 KB Output is correct
11 Correct 557 ms 54824 KB Output is correct
12 Correct 561 ms 54844 KB Output is correct
13 Correct 558 ms 54796 KB Output is correct
14 Correct 571 ms 54896 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 10 ms 25372 KB Output is correct
3 Correct 10 ms 25300 KB Output is correct
4 Correct 10 ms 25300 KB Output is correct
5 Correct 11 ms 25376 KB Output is correct
6 Correct 16 ms 25512 KB Output is correct
7 Correct 87 ms 29720 KB Output is correct
8 Correct 14 ms 25428 KB Output is correct
9 Correct 17 ms 25520 KB Output is correct
10 Correct 86 ms 29664 KB Output is correct
11 Correct 64 ms 29524 KB Output is correct
12 Correct 68 ms 29744 KB Output is correct
13 Correct 72 ms 29644 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 10 ms 25372 KB Output is correct
3 Correct 10 ms 25300 KB Output is correct
4 Correct 10 ms 25300 KB Output is correct
5 Correct 11 ms 25376 KB Output is correct
6 Correct 16 ms 25512 KB Output is correct
7 Correct 87 ms 29720 KB Output is correct
8 Correct 14 ms 25428 KB Output is correct
9 Correct 17 ms 25520 KB Output is correct
10 Correct 86 ms 29664 KB Output is correct
11 Correct 64 ms 29524 KB Output is correct
12 Correct 68 ms 29744 KB Output is correct
13 Correct 72 ms 29644 KB Output is correct
14 Correct 143 ms 31840 KB Output is correct
15 Correct 1260 ms 52692 KB Output is correct
16 Correct 138 ms 33284 KB Output is correct
17 Correct 1259 ms 55624 KB Output is correct
18 Correct 732 ms 55200 KB Output is correct
19 Correct 715 ms 55640 KB Output is correct
20 Correct 1068 ms 55752 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25320 KB Output is correct
2 Correct 9 ms 25348 KB Output is correct
3 Correct 77 ms 28616 KB Output is correct
4 Correct 605 ms 52736 KB Output is correct
5 Correct 769 ms 54944 KB Output is correct
6 Correct 1045 ms 55184 KB Output is correct
7 Correct 1152 ms 55456 KB Output is correct
8 Correct 1270 ms 55576 KB Output is correct
9 Correct 687 ms 54868 KB Output is correct
10 Correct 699 ms 54952 KB Output is correct
11 Correct 509 ms 54788 KB Output is correct
12 Correct 641 ms 55056 KB Output is correct
13 Correct 760 ms 55016 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 10 ms 25352 KB Output is correct
3 Correct 10 ms 25376 KB Output is correct
4 Correct 12 ms 25428 KB Output is correct
5 Incorrect 11 ms 25360 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25376 KB Output is correct
2 Correct 12 ms 25300 KB Output is correct
3 Correct 12 ms 25300 KB Output is correct
4 Correct 12 ms 25300 KB Output is correct
5 Incorrect 14 ms 25428 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25300 KB Output is correct
2 Correct 10 ms 25376 KB Output is correct
3 Correct 10 ms 25340 KB Output is correct
4 Correct 10 ms 25344 KB Output is correct
5 Correct 9 ms 25384 KB Output is correct
6 Correct 63 ms 28292 KB Output is correct
7 Correct 102 ms 31132 KB Output is correct
8 Correct 583 ms 54792 KB Output is correct
9 Correct 603 ms 54804 KB Output is correct
10 Correct 593 ms 54800 KB Output is correct
11 Correct 557 ms 54824 KB Output is correct
12 Correct 561 ms 54844 KB Output is correct
13 Correct 558 ms 54796 KB Output is correct
14 Correct 571 ms 54896 KB Output is correct
15 Correct 11 ms 25300 KB Output is correct
16 Correct 10 ms 25372 KB Output is correct
17 Correct 10 ms 25300 KB Output is correct
18 Correct 10 ms 25300 KB Output is correct
19 Correct 11 ms 25376 KB Output is correct
20 Correct 16 ms 25512 KB Output is correct
21 Correct 87 ms 29720 KB Output is correct
22 Correct 14 ms 25428 KB Output is correct
23 Correct 17 ms 25520 KB Output is correct
24 Correct 86 ms 29664 KB Output is correct
25 Correct 64 ms 29524 KB Output is correct
26 Correct 68 ms 29744 KB Output is correct
27 Correct 72 ms 29644 KB Output is correct
28 Correct 143 ms 31840 KB Output is correct
29 Correct 1260 ms 52692 KB Output is correct
30 Correct 138 ms 33284 KB Output is correct
31 Correct 1259 ms 55624 KB Output is correct
32 Correct 732 ms 55200 KB Output is correct
33 Correct 715 ms 55640 KB Output is correct
34 Correct 1068 ms 55752 KB Output is correct
35 Correct 11 ms 25320 KB Output is correct
36 Correct 9 ms 25348 KB Output is correct
37 Correct 77 ms 28616 KB Output is correct
38 Correct 605 ms 52736 KB Output is correct
39 Correct 769 ms 54944 KB Output is correct
40 Correct 1045 ms 55184 KB Output is correct
41 Correct 1152 ms 55456 KB Output is correct
42 Correct 1270 ms 55576 KB Output is correct
43 Correct 687 ms 54868 KB Output is correct
44 Correct 699 ms 54952 KB Output is correct
45 Correct 509 ms 54788 KB Output is correct
46 Correct 641 ms 55056 KB Output is correct
47 Correct 760 ms 55016 KB Output is correct
48 Correct 11 ms 25300 KB Output is correct
49 Correct 10 ms 25352 KB Output is correct
50 Correct 10 ms 25376 KB Output is correct
51 Correct 12 ms 25428 KB Output is correct
52 Incorrect 11 ms 25360 KB Output isn't correct
53 Halted 0 ms 0 KB -