oj.uz

Submission #452139

# Submission time Handle Problem Language Result Execution time Memory
452139 2021-08-03T21:33:29 Z rainboy Comparing Plants (IOI20_plants) C++17
44 / 100
 1046 ms 75328 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 : (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.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 Incorrect 1 ms 716 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 113 ms 5444 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 108 ms 5480 KB Output is correct
11 Correct 110 ms 5368 KB Output is correct
12 Correct 101 ms 5480 KB Output is correct
13 Correct 114 ms 5352 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 113 ms 5444 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 108 ms 5480 KB Output is correct
11 Correct 110 ms 5368 KB Output is correct
12 Correct 101 ms 5480 KB Output is correct
13 Correct 114 ms 5352 KB Output is correct
14 Correct 163 ms 11028 KB Output is correct
15 Correct 931 ms 75204 KB Output is correct
16 Correct 170 ms 11052 KB Output is correct
17 Correct 944 ms 75236 KB Output is correct
18 Correct 744 ms 75252 KB Output is correct
19 Correct 708 ms 75328 KB Output is correct
20 Correct 1046 ms 75296 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 4184 KB Output is correct
4 Correct 621 ms 75092 KB Output is correct
5 Correct 621 ms 75268 KB Output is correct
6 Correct 651 ms 75204 KB Output is correct
7 Correct 698 ms 75204 KB Output is correct
8 Correct 930 ms 75308 KB Output is correct
9 Correct 667 ms 75076 KB Output is correct
10 Correct 607 ms 75252 KB Output is correct
11 Correct 661 ms 74748 KB Output is correct
12 Correct 575 ms 75168 KB Output is correct
13 Correct 767 ms 75204 KB Output is correct

Subtask #5
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 Incorrect 1 ms 716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
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 656 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Incorrect 2 ms 1100 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
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 Incorrect 1 ms 716 KB Output isn't correct
5 Halted 0 ms 0 KB -