Submission #452072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
452072	2021-08-03T18:06:13 Z	rainboy	Comparing Plants (IOI20_plants)	C++17	44 / 100	505 ms	15844 KB

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_;

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 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 i_;

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

char gt[SMALL][SMALL];

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 {
		build(rr, n);
		i_ = -1;
		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
		return hh[x] < hh[y] ? -1 : 1;
}

Subtask #1
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	332 KB	Output is correct
2	Correct	204 KB	Output is correct
3	Correct	332 KB	Output is correct
4	Incorrect	332 KB	Output isn't correct
5	Halted	0 KB	-

Subtask #2
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	3 ms	332 KB	Output is correct
6	Correct	3 ms	436 KB	Output is correct
7	Correct	64 ms	4076 KB	Output is correct
8	Correct	4 ms	460 KB	Output is correct
9	Correct	3 ms	460 KB	Output is correct
10	Correct	64 ms	4160 KB	Output is correct
11	Correct	62 ms	3964 KB	Output is correct
12	Correct	83 ms	4272 KB	Output is correct
13	Correct	65 ms	4136 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	3 ms	332 KB	Output is correct
6	Correct	3 ms	436 KB	Output is correct
7	Correct	64 ms	4076 KB	Output is correct
8	Correct	4 ms	460 KB	Output is correct
9	Correct	3 ms	460 KB	Output is correct
10	Correct	64 ms	4160 KB	Output is correct
11	Correct	62 ms	3964 KB	Output is correct
12	Correct	83 ms	4272 KB	Output is correct
13	Correct	65 ms	4136 KB	Output is correct
14	Correct	87 ms	5220 KB	Output is correct
15	Correct	490 ms	15844 KB	Output is correct
16	Correct	87 ms	5164 KB	Output is correct
17	Correct	489 ms	15676 KB	Output is correct
18	Correct	356 ms	15628 KB	Output is correct
19	Correct	347 ms	15664 KB	Output is correct
20	Correct	505 ms	15736 KB	Output is correct

Subtask #4
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	60 ms	3908 KB	Output is correct
4	Correct	262 ms	15760 KB	Output is correct
5	Correct	268 ms	15684 KB	Output is correct
6	Correct	321 ms	15736 KB	Output is correct
7	Correct	368 ms	15684 KB	Output is correct
8	Correct	466 ms	15748 KB	Output is correct
9	Correct	259 ms	15608 KB	Output is correct
10	Correct	279 ms	15608 KB	Output is correct
11	Correct	83 ms	5316 KB	Output is correct
12	Correct	248 ms	15556 KB	Output is correct
13	Correct	328 ms	15624 KB	Output is correct

Subtask #5
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Incorrect	0 ms	204 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Incorrect	1 ms	332 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #7
0 / 25.0

#	Verdict	Memory	Grader output
1	Correct	332 KB	Output is correct
2	Correct	204 KB	Output is correct
3	Correct	332 KB	Output is correct
4	Incorrect	332 KB	Output isn't correct
5	Halted	0 KB	-

Submission #452072

Compilation message

Subtask #1 0 / 5.0

Subtask #2 14.0 / 14.0

Subtask #3 13.0 / 13.0

Subtask #4 17.0 / 17.0

Subtask #5 0 / 11.0

Subtask #6 0 / 15.0

Subtask #7 0 / 25.0

Subtask #1
0 / 5.0

Subtask #2
14.0 / 14.0

Subtask #3
13.0 / 13.0

Subtask #4
17.0 / 17.0

Subtask #5
0 / 11.0

Subtask #6
0 / 15.0

Subtask #7
0 / 25.0