Submission #452081

#	Time	Username	Problem	Language	Result	Execution time	Memory
452081		rainboy	Comparing Plants (IOI20_plants)	C++17	75 / 100	1137 ms	19500 KiB

plants

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

using namespace std;

typedef vector<int> vi;

const int SMALL = 300, N = 200000, N_ = 1 << 18, INF = 0x3f3f3f3f;

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

int pp[N], hh[N], n, k;

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

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] == i_ ? 0 : first[r] - last[l]);
	st[i] += lz[i];
}

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

void build(vi aa, int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	memset(lz, 0, n_ * 2 * sizeof *lz);
	for (i = 0; i < n_; i++) {
		st[n_ + i] = i < n ? aa[i] : INF, gap[n_ + i] = 0;
		first[n_ + i] = last[n_ + i] = i;
	}
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

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 k) {
	if (gap[1] >= k) {
		int i = 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 first[1] - last[1] + n >= k && first[1] != i_ ? first[1] : -1;
}

char gt[SMALL][SMALL];
char gt_[N], lt_[N];

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

	n = rr.size(), k = k_;
	if (n <= SMALL) {
		for (i_ = 0; i_ < n; i_++) {
			memset(gt[i_], 1, n * sizeof *gt[i_]);
			build(rr, n);
			for (h = n - 1; h >= 0; h--) {
				i = get(k);
				if (i == -1)
					break;
				gt[i_][i] = 0;
				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);
			}
		}
	} else if (k == 2) {
		for (i = 0; i < n; i++)
			pp[i] = rr[i];
		for (i = 1; i < n; i++)
			pp[i] += pp[i - 1];
	} else {
		i_ = 0, build(rr, n), memset(gt_, 1, n * sizeof *gt_);
		for (h = n - 1; h >= 0; h--) {
			i = get(k);
			if (i == -1)
				break;
			gt_[i] = 0;
			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);
		}
		for (i = 0; i < n; i++)
			rr[i] = k - 1 - rr[i];
		i_ = 0, build(rr, n), memset(lt_, 1, n * sizeof *lt_);
		for (h = n - 1; h >= 0; h--) {
			i = get(k);
			if (i == -1)
				break;
			lt_[i] = 0;
			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);
		}
		for (i = 0; i < n; i++)
			rr[i] = k - 1 - rr[i];
		i_ = -1, build(rr, n);
		for (h = n - 1; h >= 0; h--) {
			i = get(k);
			hh[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);
		}
	}
}

int compare_plants(int x, int y) {
	if (n <= SMALL)
		return !gt[x][y] && !gt[y][x] ? 0 : (gt[x][y] ? 1 : -1);
	else if (k == 2) {
		int c = pp[y - 1] - (x == 0 ? 0 : pp[x - 1]);

		if (c == y - x)
			return -1;
		else if (c == 0)
			return 1;
		c = pp[n - 1] - c;
		if (c == n - (y - x))
			return 1;
		else if (c == 0)
			return -1;
		return 0;
	} else if (x == 0)
		return !gt_[y] && !lt_[y] ? 0 : (gt_[y] ? 1 : -1);
	else
		return hh[x] < hh[y] ? -1 : 1;
}

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