oj.uz

Submission #452140

# Submission time Handle Problem Language Result Execution time Memory
452140 2021-08-03T21:37:42 Z rainboy Comparing Plants (IOI20_plants) C++17
100 / 100
 994 ms 78916 KB 
#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 : (dir == 0 ? (pp[dir][0][i] - i + n) % n : (i - pp[dir][0][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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 75 ms 3536 KB Output is correct
7 Correct 131 ms 10904 KB Output is correct
8 Correct 463 ms 74748 KB Output is correct
9 Correct 491 ms 74800 KB Output is correct
10 Correct 524 ms 74748 KB Output is correct
11 Correct 557 ms 74836 KB Output is correct
12 Correct 533 ms 74816 KB Output is correct
13 Correct 684 ms 74840 KB Output is correct
14 Correct 570 ms 74968 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 4 ms 1100 KB Output is correct
7 Correct 111 ms 5460 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 110 ms 5360 KB Output is correct
11 Correct 108 ms 5352 KB Output is correct
12 Correct 99 ms 5572 KB Output is correct
13 Correct 110 ms 5480 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 4 ms 1100 KB Output is correct
7 Correct 111 ms 5460 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 110 ms 5360 KB Output is correct
11 Correct 108 ms 5352 KB Output is correct
12 Correct 99 ms 5572 KB Output is correct
13 Correct 110 ms 5480 KB Output is correct
14 Correct 160 ms 11028 KB Output is correct
15 Correct 929 ms 75228 KB Output is correct
16 Correct 177 ms 11040 KB Output is correct
17 Correct 934 ms 75176 KB Output is correct
18 Correct 737 ms 75200 KB Output is correct
19 Correct 717 ms 75332 KB Output is correct
20 Correct 994 ms 75228 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 100 ms 4188 KB Output is correct
4 Correct 604 ms 75104 KB Output is correct
5 Correct 622 ms 75248 KB Output is correct
6 Correct 669 ms 75172 KB Output is correct
7 Correct 705 ms 75428 KB Output is correct
8 Correct 930 ms 75332 KB Output is correct
9 Correct 648 ms 75204 KB Output is correct
10 Correct 606 ms 75208 KB Output is correct
11 Correct 645 ms 74836 KB Output is correct
12 Correct 552 ms 75204 KB Output is correct
13 Correct 749 ms 75240 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 20 ms 1784 KB Output is correct
8 Correct 20 ms 1764 KB Output is correct
9 Correct 20 ms 1776 KB Output is correct
10 Correct 19 ms 1868 KB Output is correct
11 Correct 20 ms 1792 KB Output is correct
12 Correct 19 ms 1784 KB Output is correct
13 Correct 19 ms 1784 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 367 ms 76900 KB Output is correct
7 Correct 443 ms 76912 KB Output is correct
8 Correct 577 ms 76876 KB Output is correct
9 Correct 737 ms 76904 KB Output is correct
10 Correct 432 ms 76768 KB Output is correct
11 Correct 570 ms 76864 KB Output is correct
12 Correct 445 ms 76744 KB Output is correct
13 Correct 380 ms 76856 KB Output is correct
14 Correct 562 ms 76956 KB Output is correct
15 Correct 555 ms 76864 KB Output is correct
16 Correct 435 ms 76668 KB Output is correct
17 Correct 367 ms 76840 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 75 ms 3536 KB Output is correct
7 Correct 131 ms 10904 KB Output is correct
8 Correct 463 ms 74748 KB Output is correct
9 Correct 491 ms 74800 KB Output is correct
10 Correct 524 ms 74748 KB Output is correct
11 Correct 557 ms 74836 KB Output is correct
12 Correct 533 ms 74816 KB Output is correct
13 Correct 684 ms 74840 KB Output is correct
14 Correct 570 ms 74968 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 1 ms 716 KB Output is correct
17 Correct 1 ms 716 KB Output is correct
18 Correct 1 ms 716 KB Output is correct
19 Correct 1 ms 716 KB Output is correct
20 Correct 4 ms 1100 KB Output is correct
21 Correct 111 ms 5460 KB Output is correct
22 Correct 2 ms 844 KB Output is correct
23 Correct 4 ms 1100 KB Output is correct
24 Correct 110 ms 5360 KB Output is correct
25 Correct 108 ms 5352 KB Output is correct
26 Correct 99 ms 5572 KB Output is correct
27 Correct 110 ms 5480 KB Output is correct
28 Correct 160 ms 11028 KB Output is correct
29 Correct 929 ms 75228 KB Output is correct
30 Correct 177 ms 11040 KB Output is correct
31 Correct 934 ms 75176 KB Output is correct
32 Correct 737 ms 75200 KB Output is correct
33 Correct 717 ms 75332 KB Output is correct
34 Correct 994 ms 75228 KB Output is correct
35 Correct 1 ms 716 KB Output is correct
36 Correct 1 ms 716 KB Output is correct
37 Correct 100 ms 4188 KB Output is correct
38 Correct 604 ms 75104 KB Output is correct
39 Correct 622 ms 75248 KB Output is correct
40 Correct 669 ms 75172 KB Output is correct
41 Correct 705 ms 75428 KB Output is correct
42 Correct 930 ms 75332 KB Output is correct
43 Correct 648 ms 75204 KB Output is correct
44 Correct 606 ms 75208 KB Output is correct
45 Correct 645 ms 74836 KB Output is correct
46 Correct 552 ms 75204 KB Output is correct
47 Correct 749 ms 75240 KB Output is correct
48 Correct 1 ms 716 KB Output is correct
49 Correct 1 ms 716 KB Output is correct
50 Correct 1 ms 716 KB Output is correct
51 Correct 1 ms 716 KB Output is correct
52 Correct 1 ms 716 KB Output is correct
53 Correct 3 ms 816 KB Output is correct
54 Correct 20 ms 1784 KB Output is correct
55 Correct 20 ms 1764 KB Output is correct
56 Correct 20 ms 1776 KB Output is correct
57 Correct 19 ms 1868 KB Output is correct
58 Correct 20 ms 1792 KB Output is correct
59 Correct 19 ms 1784 KB Output is correct
60 Correct 19 ms 1784 KB Output is correct
61 Correct 94 ms 5568 KB Output is correct
62 Correct 140 ms 13096 KB Output is correct
63 Correct 515 ms 78020 KB Output is correct
64 Correct 599 ms 78300 KB Output is correct
65 Correct 633 ms 78472 KB Output is correct
66 Correct 714 ms 78660 KB Output is correct
67 Correct 913 ms 78916 KB Output is correct
68 Correct 601 ms 78140 KB Output is correct
69 Correct 626 ms 78828 KB Output is correct
70 Correct 639 ms 78000 KB Output is correct
71 Correct 651 ms 78280 KB Output is correct
72 Correct 669 ms 78492 KB Output is correct
73 Correct 683 ms 78660 KB Output is correct
74 Correct 504 ms 78088 KB Output is correct
75 Correct 569 ms 78404 KB Output is correct