oj.uz

Submission #1021002

# Submission time Handle Problem Language Result Execution time Memory
1021002 2024-07-12T12:46:43 Z j_vdd16 Comparing Plants (IOI20_plants) C++17
55 / 100
 2479 ms 34512 KB 
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef tuple<int, int, int> iii;

typedef uint64_t u64;
typedef int64_t i64;

int k;
struct SegTree {
	const iii id = { INT_MAX / 2, -1, 0 };
	vector<iii> tree;
	vi lazySub;
	int n, N;

	SegTree(vi v) {
		n = v.size();
		N = 1;
		while (N < n)
			N *= 2;

		tree.resize(2 * N, id);
		lazySub.resize(2 * N, 0);
		loop(i, n)
			tree[N + i] = { v[i], i, i };

		for (int i = N - 1; i >= 1; i--)
			tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
	}

	iii merge(iii a, iii b) {
		auto [v1, i1, r1] = a;
		auto [v2, i2, r2] = b;

		if (v1 < v2)
			return a;

		if (v2 < v1)
			return b;

		int v = v1, i, r = r2;
		if (i2 - r1 >= k)
			i = i2;
		else
			i = i1;

		return { v, i, r };
	}

	void rangeSub(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
		if (tr == -1)
			tr = N;

		if (tl >= r || tr <= l)
			return;

		if (tl >= l && tr <= r)
		{
			get<0>(tree[i]) -= v;
			lazySub[i] += v;
			return;
		}

		if (i < N)
		{
			lazySub[2 * i] += lazySub[i];
			lazySub[2 * i + 1] += lazySub[i];
			get<0>(tree[2 * i]) -= lazySub[i];
			get<0>(tree[2 * i + 1]) -= lazySub[i];
		}
		lazySub[i] = 0;

		int tm = (tl + tr) / 2;
		rangeSub(l, r, v, i * 2, tl, tm);
		rangeSub(l, r, v, i * 2 + 1, tm, tr);

		tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
	}
	iii range(int l, int r, int i = 1, int tl = 0, int tr = -1) {
		if (tr == -1)
			tr = N;

		if (tl >= r || tr <= l)
			return id;

		if (tl >= l && tr <= r)
			return tree[i];

		if (i < N)
		{
			lazySub[2 * i] += lazySub[i];
			lazySub[2 * i + 1] += lazySub[i];
			get<0>(tree[2 * i]) -= lazySub[i];
			get<0>(tree[2 * i + 1]) -= lazySub[i];
		}
		lazySub[i] = 0;

		int tm = (tl + tr) / 2;
		return merge(range(l, r, i * 2, tl, tm), range(l, r, i * 2 + 1, tm, tr));
	}

	void set(int pos, int v, int i = 1, int tl = 0, int tr = -1) {
		if (tr == -1)
			tr = N;

		if (i >= N)
		{
			get<0>(tree[i]) = v;
			return;
		}

		if (i < N)
		{
			lazySub[2 * i] += lazySub[i];
			lazySub[2 * i + 1] += lazySub[i];
			get<0>(tree[2 * i]) -= lazySub[i];
			get<0>(tree[2 * i + 1]) -= lazySub[i];
		}
		lazySub[i] = 0;

		int tm = (tl + tr) / 2;
		if (pos < tm)
			set(pos, v, i * 2, tl, tm);
		else
			set(pos, v, i * 2 + 1, tm, tr);

		tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
	}
};

struct MaxTree
{
	const ii id = { -1, -1 };
	vii tree;
	int n, N;

	MaxTree(vi v) {
		n = v.size();
		N = 1;
		while (N < n)
			N *= 2;

		tree.resize(2 * N, id);
		loop(i, n)
			tree[N + i] = { v[i], i };

		for (int i = N - 1; i >= 1; i--)
			tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
	}

	ii merge(ii a, ii b) {
		if (a.first > b.first)
			return a;
		else
			return b;
	}

	ii range(int l, int r, int i = 1, int tl = 0, int tr = -1) {
		if (tr == -1)
			tr = N;

		if (tl >= r || tr <= l)
			return id;

		if (tl >= l && tr <= r)
			return tree[i];

		int tm = (tl + tr) / 2;
		return merge(range(l, r, i * 2, tl, tm), range(l, r, i * 2 + 1, tm, tr));
	}
};

int n;
vi r;

vi perm;
vii neighbors;
void init(int _k, vi _r)
{
	n = _r.size();
	k = _k;
	r = _r;
	perm.assign(n, 0);

	SegTree segTree(r);

	int idx = n - 1;
	vb vis(n);

	/*cout << "R: ";
	for (int x : r)
	cout << x << ' ';
	cout << endl;
	cout << "Low: ";*/
	while (idx >= 0)
	{
		auto [lowVal, low, maxR] = segTree.range(0, n);
		//cout << low << ' ';
		if (low - k + 1 < 0)
		{
			segTree.rangeSub(0, low, 1);
			segTree.rangeSub(n + low - k + 1, n, 1);
		}
		else
		{
			segTree.rangeSub(low - k + 1, low, 1);
		}

		segTree.set(low, INT_MAX / 2);
		vis[low] = true;
		perm[low] = idx--;
	}

	map<int, int> prev;
	map<int, int> next;
	for (int i = 1; i < k; i++)
		next.insert({ perm[i], i });
	for (int i = n - 1; i > n - k; i--)
		prev.insert({ perm[i], i });

	neighbors.assign(n, { -1, -1 });
	loop(i, n)
	{
		auto prevIt = prev.upper_bound(perm[i]);
		auto nextIt = next.upper_bound(perm[i]);

		if (prevIt != prev.begin())
			neighbors[i].first = (--prevIt)->second;

		if (nextIt != next.begin())
			neighbors[i].second = (--nextIt)->second;

		next.insert({ perm[(i + k) % n], (i + k) % n });
		next.erase(perm[(i + 1) % n]);

		prev.insert({ perm[(i) % n], (i) % n });
		prev.erase(perm[(n + i - k + 1) % n]);
	}
	/*cout << endl;
	cout << "Perm: ";
	for (int x : perm)
	cout << x << ' ';
	cout << endl;*/
}

int compare_plants(int x, int y)
{
	if (perm[x] < perm[y])
	{
		if (n > 5000)
			return -1;

		stack<int> s;
		s.push(y);

		vb vis(n);
		vis[y] = true;
		while (s.size())
		{
			int node = s.top();
			s.pop();

			if (node == x)
				return -1;

			auto [n1, n2] = neighbors[node];
			if (n1 != -1 && !vis[n1] && perm[n1] >= perm[x]) {
				vis[n1] = true;
				s.push(n1);
			}
			if (n2 != -1 && !vis[n2] && perm[n2] >= perm[x]) {
				vis[n2] = true;
				s.push(n2);
			}
		}
	}
	else if (perm[x] > perm[y])
	{
		if (n > 5000)
			return 1;

		stack<int> s;
		s.push(x);

		vb vis(n);
		vis[x] = true;
		while (s.size())
		{
			int node = s.top();
			s.pop();

			if (node == y)
				return 1;

			auto [n1, n2] = neighbors[node];
			if (n1 != -1 && !vis[n1] && perm[n1] >= perm[y]) {
				vis[n1] = true;
				s.push(n1);
			}
			if (n2 != -1 && !vis[n2] && perm[n2] >= perm[y]) {
				vis[n2] = true;
				s.push(n2);
			}
		}
	}

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 46 ms 3052 KB Output is correct
7 Incorrect 48 ms 4180 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 11 ms 604 KB Output is correct
7 Correct 2391 ms 3588 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 11 ms 616 KB Output is correct
10 Correct 2175 ms 3724 KB Output is correct
11 Correct 2479 ms 3444 KB Output is correct
12 Correct 1294 ms 3724 KB Output is correct
13 Correct 2461 ms 3692 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 11 ms 604 KB Output is correct
7 Correct 2391 ms 3588 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 11 ms 616 KB Output is correct
10 Correct 2175 ms 3724 KB Output is correct
11 Correct 2479 ms 3444 KB Output is correct
12 Correct 1294 ms 3724 KB Output is correct
13 Correct 2461 ms 3692 KB Output is correct
14 Correct 80 ms 5204 KB Output is correct
15 Correct 646 ms 27324 KB Output is correct
16 Correct 77 ms 5204 KB Output is correct
17 Correct 645 ms 27204 KB Output is correct
18 Correct 309 ms 24900 KB Output is correct
19 Correct 349 ms 25064 KB Output is correct
20 Correct 636 ms 34512 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 653 ms 3148 KB Output is correct
4 Correct 189 ms 15680 KB Output is correct
5 Correct 240 ms 15736 KB Output is correct
6 Correct 315 ms 15692 KB Output is correct
7 Correct 406 ms 16584 KB Output is correct
8 Correct 593 ms 24132 KB Output is correct
9 Correct 224 ms 15576 KB Output is correct
10 Correct 227 ms 15592 KB Output is correct
11 Correct 171 ms 15684 KB Output is correct
12 Correct 190 ms 15680 KB Output is correct
13 Correct 288 ms 21568 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 18 ms 968 KB Output is correct
8 Correct 26 ms 856 KB Output is correct
9 Correct 26 ms 860 KB Output is correct
10 Correct 25 ms 972 KB Output is correct
11 Correct 21 ms 988 KB Output is correct
12 Correct 20 ms 856 KB Output is correct
13 Correct 34 ms 1108 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Incorrect 256 ms 15696 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 46 ms 3052 KB Output is correct
7 Incorrect 48 ms 4180 KB Output isn't correct
8 Halted 0 ms 0 KB -