oj.uz

Submission #1020994

# Submission time Handle Problem Language Result Execution time Memory
1020994 2024-07-12T12:43:05 Z j_vdd16 Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 18612 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]) {
				vis[n1] = true;
				s.push(n1);
			}
			if (n2 != -1 && !vis[n2]) {
				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]) {
				vis[n1] = true;
				s.push(n1);
			}
			if (n2 != -1 && !vis[n2]) {
				vis[n2] = true;
				s.push(n2);
			}
		}
	}

	return 0;
}

Subtask #1
0 / 5.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 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 42 ms 4088 KB Output is correct
7 Correct 225 ms 6484 KB Output is correct
8 Correct 265 ms 18496 KB Output is correct
9 Correct 390 ms 18612 KB Output is correct
10 Correct 1571 ms 18496 KB Output is correct
11 Execution timed out 4062 ms 18500 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 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 15 ms 616 KB Output is correct
7 Correct 2805 ms 3580 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 13 ms 544 KB Output is correct
10 Correct 2885 ms 3640 KB Output is correct
11 Correct 2951 ms 3476 KB Output is correct
12 Correct 2254 ms 3700 KB Output is correct
13 Correct 2479 ms 3676 KB Output is correct

Subtask #3
0 / 13.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 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 15 ms 616 KB Output is correct
7 Correct 2805 ms 3580 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 13 ms 544 KB Output is correct
10 Correct 2885 ms 3640 KB Output is correct
11 Correct 2951 ms 3476 KB Output is correct
12 Correct 2254 ms 3700 KB Output is correct
13 Correct 2479 ms 3676 KB Output is correct
14 Execution timed out 4006 ms 5204 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 847 ms 3268 KB Output is correct
4 Execution timed out 4014 ms 15676 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 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 436 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 24 ms 1212 KB Output is correct
8 Correct 42 ms 1364 KB Output is correct
9 Correct 39 ms 1364 KB Output is correct
10 Correct 42 ms 1360 KB Output is correct
11 Correct 23 ms 1364 KB Output is correct
12 Correct 31 ms 1304 KB Output is correct
13 Correct 38 ms 1396 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 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Execution timed out 4090 ms 18012 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 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 42 ms 4088 KB Output is correct
7 Correct 225 ms 6484 KB Output is correct
8 Correct 265 ms 18496 KB Output is correct
9 Correct 390 ms 18612 KB Output is correct
10 Correct 1571 ms 18496 KB Output is correct
11 Execution timed out 4062 ms 18500 KB Time limit exceeded
12 Halted 0 ms 0 KB -