Submission #452139

#	Time	Username	Problem	Language	Result	Execution time	Memory
452139		rainboy	Comparing Plants (IOI20_plants)	C++17	44 / 100	1046 ms	75328 KiB

plants

#include "plants.h"
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 200000, LN = 18, N_ = 1 << LN, INF = 0x3f3f3f3f;	/* LN = ceil(log2(N)) */

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int aa[N], ii[N], n, k;

int st[N_ * 2], lz[N_ * 2], first[N_ * 2], last[N_ * 2], gap[N_ * 2], n_;

void put(int i, int x) {
	st[i] += x, lz[i] += x;
}

void pul(int i) {
	int l = i << 1, r = l | 1;

	if (st[l] < st[r])
		st[i] = st[l], first[i] = first[l], last[i] = last[l], gap[i] = gap[l];
	else if (st[l] > st[r])
		st[i] = st[r], first[i] = first[r], last[i] = last[r], gap[i] = gap[r];
	else
		st[i] = st[l], first[i] = first[l], last[i] = last[r], gap[i] = max(max(gap[l], gap[r]), first[r] - last[l]);
	st[i] += lz[i];
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void update(int l, int r, int x) {
	int l_ = l += n_, r_ = r += n_;

	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, x);
		if ((r & 1) == 0)
			put(r--, x);
	}
	pull(l_), pull(r_);
}

int get() {
	int i = 1;

	if (gap[1] < k)
		return first[1];
	while (i < n_)
		if (st[i] == st[i << 1 | 0] + lz[i] && gap[i << 1 | 0] >= k)
			i = i << 1 | 0;
		else if (st[i] == st[i << 1 | 1] + lz[i] && gap[i << 1 | 1] >= k)
			i = i << 1 | 1;
		else
			return first[i << 1 | 1];
	return -1;
}

void update_(int l, int r, int x) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			st[l++] = x;
		if ((r & 1) == 0)
			st[r--] = x;
	}
}

int query_(int i) {
	int x = INF;

	for (i += n_; i > 0; i >>= 1)
		x = min(x, st[i]);
	return x;
}

char root[N]; int pp[2][LN + 1][N], dd[2][LN + 1][N];

void init(int k_, vi rr) {
	int h, h_, i, dir, l;

	n = rr.size(), k = k_;
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++) {
		st[n_ + i] = i < n ? rr[i] : INF, gap[n_ + i] = 0;
		first[n_ + i] = last[n_ + i] = i;
	}
	for (i = n_ - 1; i > 0; i--)
		pul(i);
	for (h = n - 1; h >= 0; h--) {
		i = get();
		aa[ii[h] = i] = h;
		update(i, i, INF);
		if (i >= k - 1)
			update(i - k + 1, i, -1);
		else
			update(0, i, -1), update(i - k + 1 + n, n - 1, -1);
	}
	memset(st, 0x3f, n_ * 2 * sizeof *st);
	for (h = n - 1; h >= 0; h--) {
		i = ii[h], h_ = query_(i);
		if (h_ == INF)
			root[i] = 1, pp[0][0][i] = -1;
		else
			root[i] = 0, pp[0][0][i] = ii[h_];
		if (i >= k - 1)
			update_(i - k + 1, i, h);
		else
			update_(0, i, h), update_(i - k + 1 + n, n - 1, h);
	}
	memset(st, 0x3f, n_ * 2 * sizeof *st);
	for (h = n - 1; h >= 0; h--) {
		i = ii[h], h_ = query_(i);
		if (h_ == INF)
			root[i] = 1, pp[1][0][i] = -1;
		else
			root[i] = 0, pp[1][0][i] = ii[h_];
		if (i + k - 1 < n)
			update_(i, i + k - 1, h);
		else
			update_(i, n - 1, h), update_(0, i + k - 1 - n, h);
	}
	for (dir = 0; dir < 2; dir++) {
		for (i = 0; i < n; i++)
			dd[dir][0][i] = pp[dir][0][i] == -1 ? 0 : (pp[dir][0][i] - i + n) % n;
		for (l = 1; l <= LN; l++)
			for (i = 0; i < n; i++) {
				int p = pp[dir][l - 1][i];

				pp[dir][l][i] = p == -1 ? -1 : pp[dir][l - 1][p];
				dd[dir][l][i] = min(dd[dir][l - 1][i] + (p == -1 ? 0 : dd[dir][l - 1][p]), n);
			}
	}
}

int reachable(int i, int j, int dir) {
	int d_, l, p, d;

	if (aa[i] > aa[j])
		return 0;
	d_ = dir == 0 ? (j - i + n) % n : (i - j + n) % n;
	d = 0;
	for (l = LN; l >= 0; l--)
		if ((p = pp[dir][l][i]) != -1 && aa[p] <= aa[j])
			d = min(d + dd[dir][l][i], n), i = p;
	return d >= d_;
}

int compare_plants(int x, int y) {
	if (reachable(x, y, 0) || reachable(x, y, 1))
		return -1;
	else if (reachable(y, x, 0) || reachable(y, x, 1))
		return 1;
	else
		return 0;
}

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