제출 #1205198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205198		bangan	식물 비교 (IOI20_plants)	C++20	0 / 100	1 ms	328 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

struct Node {
	int pos, val;
	Node(int pos_ = 0, int val_ = 0): pos(pos_), val(val_) {}

	Node friend operator+ (Node a, Node b) {
		if (a.val == b.val) {
			return a.pos < b.pos ? a : b;
		} else {
			return a.val < b.val ? a : b;
		}
	}
};

struct SegmentTree {
	#define lc (v << 1)
	#define rc (v << 1 | 1)
	#define mid (l + r) / 2

	int n;
	std::vector<Node> a;
	std::vector<int> b;
	SegmentTree(int n_): n(n_), a(4 * n + 1), b(4 * n + 1, 0) {}

	void push(int v) {
		if (a[v].val != n) {
			a[v].val += b[v];
		}
		if (lc <= 4 * n) {
			b[lc] += b[v];
		}
		if (rc <= 4 * n) {
			b[rc] += b[v];
		}
		b[v] = 0;
	}

	void set_val(int i, int x, int v, int l, int r) {
		push(v);
		if (r - l == 1) {
			a[v] = Node(i, x);
			return;
		}

		i < mid ? set_val(i, x, lc, l, mid) : set_val(i, x, rc, mid, r);

		push(lc);
		push(rc);
		a[v] = a[lc] + a[rc];
	}
	void set_val(int i, int x) {
		set_val(i, x, 1, 0, n);
	}

	void update(int s, int e, int x, int v, int l, int r) {
		push(v);
		if (s <= l && r <= e) {
			b[v] += x;
			push(v);
			return;
		}

		if (s < mid) {
			update(s, e, x, lc, l, mid);
		}
		if (e > mid) {
			update(s, e, x, rc, mid, r);
		}

		push(lc);
		push(rc);
		a[v] = a[lc] + a[rc];
	}
	void update(int s, int e, int x) {
		update(s, e, x, 1, 0, n);
	};

	Node get(int s, int e, int v, int l, int r) {
		push(v);
		if (s <= l && r <= e) {
			return a[v];
		}

		if (e <= mid) {
			return get(s, e, lc, l, mid);
		} else if (s >= mid) {
			return get(s, e, rc, mid, r);
		} else {
			return get(s, e, lc, l, mid) + get(s, e, rc, mid, r);
		}
	}
	Node get(int s, int e) {
		return get(s, e, 1, 0, n);
	}
};

constexpr int N = 2E5;

int n, h[2 * N];
std::bitset<N> less, more;

void init(int k, std::vector<int> org_r) {
	n = org_r.size();

	auto norm = [&](int i) {
		i %= n;
		if (i < 0) {
			return i + n;
		} else {
			return i;
		}
	};

	SegmentTree r(n);
	for (int i = 0; i < n; i++) {
		r.set_val(i, org_r[i]);
	}
	auto get = [&](int s, int e) -> Node {
		s = norm(s);
		e = norm(e);
		// std::cout << "(s, e) = (" << s << ", " << e << ")\n";
		if (s <= e) {
			return r.get(s, e + 1);
		} else {
			return r.get(s, n) + r.get(0, e + 1);
		}
	};
	auto update = [&](int s, int e, int x) {
		s = norm(s);
		e = norm(e);
		if (s <= e) {
			r.update(s, e + 1, x);
		} else {
			r.update(s, n, x);
			r.update(0, e + 1, x);
		}
	};

	std::vector<int> ord;
	auto dec = [&](auto self, int i) -> void {
		while (get(i - k + 1, i - 1).val == 0) {
			self(self, get(i - k + 1, i - 1).pos);
		}

		ord.push_back(i);
		r.set_val(i, n);
		update(i - k + 1, i - 1, -1);
	};
	while (get(0, n - 1).val < n) {
		int i = get(0, n - 1).pos;
		dec(dec, i);
	}
	for (int i = 0; i < n; i++) {
		h[ord[i]] = n - i - 1;
	}
	for (int i = n; i < 2 * n; i++) {
		h[i] = h[i - n];
	}

	std::vector<int> L(2 * n);
	for (int i = 0; i < 2 * n; i++) {
		L[i] = i - 1;
		while (0 <= L[i] && h[L[i]] > h[i]) {
			L[i] = L[L[i]];
		}
	}
	std::vector<int> R(2 * n);
	for (int i = 2 * n - 1; i >= 0; i--) {
		R[i] = i + 1;
		while (R[i] < 2 * n && h[R[i]] > h[i]) {
			R[i] = R[R[i]];
		}
	}

	std::vector<std::vector<int>> out(n);
	for (int i = 0; i < 2 * n; i++) {
		if (L[i] != -1 && i - L[i] < k) {
			out[norm(i)].push_back(norm(L[i]));
		}
		if (R[i] != 2 * n && R[i] - i < k) {
			out[norm(i)].push_back(norm(R[i]));
		}
	}

	auto dfs0 = [&](auto self, int v) -> void {
		less[v] = true;
		for (int u : out[v]) {
			if (!less[u]) {
				self(self, u);
			}
		}
	};
	dfs0(dfs0, 0);

	for (int i = 0; i < 2 * n; i++) {
		L[i] = i - 1;
		while (0 <= L[i] && h[L[i]] < h[i]) {
			L[i] = L[L[i]];
		}
	}
	for (int i = 2 * n - 1; i >= 0; i--) {
		R[i] = i + 1;
		while (R[i] < 2 * n && h[R[i]] < h[i]) {
			R[i] = R[R[i]];
		}
	}

	std::vector<std::vector<int>> in(n);
	for (int i = 0; i < 2 * n; i++) {
		if (L[i] != -1 && i - L[i] < k) {
			in[norm(i)].push_back(norm(L[i]));
		}
		if (R[i] != 2 * n && R[i] - i < k) {
			in[norm(i)].push_back(norm(R[i]));
		}
	}

	auto dfs1 = [&](auto self, int v) -> void {
		more[v] = true;
		for (int u : in[v]) {
			if (!more[u]) {
				self(self, u);
			}
		}
	};
	dfs1(dfs1, 0);

	return;
}

int compare_plants(int x, int y) {
	assert(x == 0);
	if (less[y] == more[y]) {
		return 0;
	} else if (less[y]) {
		return 1;
	} else {
		return -1;
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25