oj.uz

Submission #452081

# Submission time Handle Problem Language Result Execution time Memory
452081 2021-08-03T18:16:57 Z rainboy Comparing Plants (IOI20_plants) C++17
75 / 100
 1137 ms 19500 KB 
#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.0 / 5.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 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 56 ms 3428 KB Output is correct
7 Correct 66 ms 3848 KB Output is correct
8 Correct 94 ms 5436 KB Output is correct
9 Correct 99 ms 5500 KB Output is correct
10 Correct 91 ms 5456 KB Output is correct
11 Correct 95 ms 5396 KB Output is correct
12 Correct 86 ms 5420 KB Output is correct
13 Correct 88 ms 5424 KB Output is correct
14 Correct 105 ms 5440 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 77 ms 3924 KB Output is correct
8 Correct 5 ms 460 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 71 ms 4040 KB Output is correct
11 Correct 66 ms 4184 KB Output is correct
12 Correct 75 ms 4336 KB Output is correct
13 Correct 80 ms 4312 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 77 ms 3924 KB Output is correct
8 Correct 5 ms 460 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 71 ms 4040 KB Output is correct
11 Correct 66 ms 4184 KB Output is correct
12 Correct 75 ms 4336 KB Output is correct
13 Correct 80 ms 4312 KB Output is correct
14 Correct 121 ms 5444 KB Output is correct
15 Correct 1033 ms 17176 KB Output is correct
16 Correct 143 ms 5784 KB Output is correct
17 Correct 1105 ms 17440 KB Output is correct
18 Correct 702 ms 17540 KB Output is correct
19 Correct 745 ms 17412 KB Output is correct
20 Correct 1137 ms 17852 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 63 ms 4216 KB Output is correct
4 Correct 560 ms 17580 KB Output is correct
5 Correct 617 ms 17792 KB Output is correct
6 Correct 767 ms 17756 KB Output is correct
7 Correct 759 ms 18184 KB Output is correct
8 Correct 1000 ms 18696 KB Output is correct
9 Correct 676 ms 19116 KB Output is correct
10 Correct 497 ms 19144 KB Output is correct
11 Correct 97 ms 7840 KB Output is correct
12 Correct 446 ms 19484 KB Output is correct
13 Correct 587 ms 19500 KB Output is correct

Subtask #5
11.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 Correct 0 ms 284 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 54 ms 1356 KB Output is correct
8 Correct 53 ms 1264 KB Output is correct
9 Correct 65 ms 1252 KB Output is correct
10 Correct 55 ms 1384 KB Output is correct
11 Correct 52 ms 1372 KB Output is correct
12 Correct 43 ms 1360 KB Output is correct
13 Correct 49 ms 1352 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 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 654 ms 18548 KB Output is correct
7 Correct 684 ms 18864 KB Output is correct
8 Correct 741 ms 19116 KB Output is correct
9 Correct 931 ms 19228 KB Output is correct
10 Correct 638 ms 18484 KB Output is correct
11 Correct 676 ms 19196 KB Output is correct
12 Correct 497 ms 18464 KB Output is correct
13 Correct 589 ms 18632 KB Output is correct
14 Correct 570 ms 18816 KB Output is correct
15 Correct 668 ms 18996 KB Output is correct
16 Correct 477 ms 18508 KB Output is correct
17 Correct 572 ms 18596 KB Output is correct

Subtask #7
0 / 25.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 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 56 ms 3428 KB Output is correct
7 Correct 66 ms 3848 KB Output is correct
8 Correct 94 ms 5436 KB Output is correct
9 Correct 99 ms 5500 KB Output is correct
10 Correct 91 ms 5456 KB Output is correct
11 Correct 95 ms 5396 KB Output is correct
12 Correct 86 ms 5420 KB Output is correct
13 Correct 88 ms 5424 KB Output is correct
14 Correct 105 ms 5440 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 5 ms 332 KB Output is correct
20 Correct 4 ms 460 KB Output is correct
21 Correct 77 ms 3924 KB Output is correct
22 Correct 5 ms 460 KB Output is correct
23 Correct 5 ms 460 KB Output is correct
24 Correct 71 ms 4040 KB Output is correct
25 Correct 66 ms 4184 KB Output is correct
26 Correct 75 ms 4336 KB Output is correct
27 Correct 80 ms 4312 KB Output is correct
28 Correct 121 ms 5444 KB Output is correct
29 Correct 1033 ms 17176 KB Output is correct
30 Correct 143 ms 5784 KB Output is correct
31 Correct 1105 ms 17440 KB Output is correct
32 Correct 702 ms 17540 KB Output is correct
33 Correct 745 ms 17412 KB Output is correct
34 Correct 1137 ms 17852 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 63 ms 4216 KB Output is correct
38 Correct 560 ms 17580 KB Output is correct
39 Correct 617 ms 17792 KB Output is correct
40 Correct 767 ms 17756 KB Output is correct
41 Correct 759 ms 18184 KB Output is correct
42 Correct 1000 ms 18696 KB Output is correct
43 Correct 676 ms 19116 KB Output is correct
44 Correct 497 ms 19144 KB Output is correct
45 Correct 97 ms 7840 KB Output is correct
46 Correct 446 ms 19484 KB Output is correct
47 Correct 587 ms 19500 KB Output is correct
48 Correct 0 ms 332 KB Output is correct
49 Correct 1 ms 332 KB Output is correct
50 Correct 0 ms 284 KB Output is correct
51 Correct 0 ms 332 KB Output is correct
52 Correct 1 ms 288 KB Output is correct
53 Correct 5 ms 460 KB Output is correct
54 Correct 54 ms 1356 KB Output is correct
55 Correct 53 ms 1264 KB Output is correct
56 Correct 65 ms 1252 KB Output is correct
57 Correct 55 ms 1384 KB Output is correct
58 Correct 52 ms 1372 KB Output is correct
59 Correct 43 ms 1360 KB Output is correct
60 Correct 49 ms 1352 KB Output is correct
61 Incorrect 62 ms 4948 KB Output isn't correct
62 Halted 0 ms 0 KB -