oj.uz

Submission #452137

# Submission time Handle Problem Language Result Execution time Memory
452137 2021-08-03T21:24:27 Z rainboy Comparing Plants (IOI20_plants) C++17
5 / 100
 678 ms 73348 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 (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 l, p, d;

	if (aa[i] > aa[j])
		return 0;
	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 >= (dir == 0 ? (j - i + n) % n : (i - j + n) % n);
}

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 656 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 76 ms 3544 KB Output is correct
7 Correct 139 ms 10904 KB Output is correct
8 Correct 517 ms 73188 KB Output is correct
9 Correct 486 ms 73284 KB Output is correct
10 Correct 522 ms 73196 KB Output is correct
11 Correct 569 ms 73284 KB Output is correct
12 Correct 564 ms 73348 KB Output is correct
13 Correct 678 ms 73280 KB Output is correct
14 Correct 570 ms 73192 KB Output is correct

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

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

Subtask #4
0 / 17.0

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

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 656 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 76 ms 3544 KB Output is correct
7 Correct 139 ms 10904 KB Output is correct
8 Correct 517 ms 73188 KB Output is correct
9 Correct 486 ms 73284 KB Output is correct
10 Correct 522 ms 73196 KB Output is correct
11 Correct 569 ms 73284 KB Output is correct
12 Correct 564 ms 73348 KB Output is correct
13 Correct 678 ms 73280 KB Output is correct
14 Correct 570 ms 73192 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 Incorrect 1 ms 716 KB Output isn't correct
20 Halted 0 ms 0 KB -