Submission #1020994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020994		j_vdd16	Comparing Plants (IOI20_plants)	C++17	25 / 100	4090 ms	18612 KiB

plants

#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
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25