oj.uz

Submission #1020999

# Submission time Handle Problem Language Result Execution time Memory
1020999 2024-07-12T12:45:02 Z j_vdd16 Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 15936 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])
	{
		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])
	{
		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;
}

#include <random>
void test()
{
	std::random_device rd;
	std::mt19937 g(rd());


	int n;
	cin >> n;

	int _k;
	cin >> _k;

	loop(i, 1000)
	{
		vi permOrig(n);
		iota(all(permOrig), 0);
		std::shuffle(all(permOrig), g);

		permOrig.insert(permOrig.end(), all(permOrig));
		vi _r(n);
		loop(j, n)
		{
			loop(j2, _k)
			{
				_r[j] += permOrig[j] < permOrig[j + j2];
			}
		}

		init(_k, _r);

		vi _r2(n);
		perm.insert(perm.end(), all(perm));
		loop(j, n)
		{
			loop(j2, _k)
			{
				_r2[j] += perm[j] < perm[j + j2];
			}
		}

		if (_r != _r2)
		{
			perm.resize(n);
			permOrig.resize(n);

			cout << "R   : ";
			for (int x : _r)
				cout << x << ' ';
			cout << endl;

			cout << "Orig: ";
			for (int x : permOrig)
				cout << x << ' ';
			cout << endl;

			cout << "Perm: ";
			for (int x : perm)
				cout << x << ' ';
			cout << endl;

			break;
		}
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 44 ms 3052 KB Output is correct
7 Correct 210 ms 4188 KB Output is correct
8 Correct 258 ms 15592 KB Output is correct
9 Correct 377 ms 15684 KB Output is correct
10 Correct 1470 ms 15684 KB Output is correct
11 Execution timed out 4026 ms 15936 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 11 ms 604 KB Output is correct
7 Correct 2447 ms 3588 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 11 ms 604 KB Output is correct
10 Correct 2185 ms 3724 KB Output is correct
11 Correct 2508 ms 3468 KB Output is correct
12 Correct 1302 ms 3728 KB Output is correct
13 Correct 2529 ms 3680 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 11 ms 604 KB Output is correct
7 Correct 2447 ms 3588 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 11 ms 604 KB Output is correct
10 Correct 2185 ms 3724 KB Output is correct
11 Correct 2508 ms 3468 KB Output is correct
12 Correct 1302 ms 3728 KB Output is correct
13 Correct 2529 ms 3680 KB Output is correct
14 Execution timed out 4069 ms 5172 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 641 ms 3152 KB Output is correct
4 Execution timed out 4069 ms 15712 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.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 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 16 ms 996 KB Output is correct
8 Correct 25 ms 1116 KB Output is correct
9 Correct 27 ms 860 KB Output is correct
10 Correct 26 ms 856 KB Output is correct
11 Correct 21 ms 860 KB Output is correct
12 Correct 22 ms 976 KB Output is correct
13 Correct 34 ms 1104 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 Execution timed out 4100 ms 15696 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 44 ms 3052 KB Output is correct
7 Correct 210 ms 4188 KB Output is correct
8 Correct 258 ms 15592 KB Output is correct
9 Correct 377 ms 15684 KB Output is correct
10 Correct 1470 ms 15684 KB Output is correct
11 Execution timed out 4026 ms 15936 KB Time limit exceeded
12 Halted 0 ms 0 KB -