oj.uz

Submission #1046296

# Submission time Handle Problem Language Result Execution time Memory
1046296 2024-08-06T12:36:29 Z thinknoexit Comparing Plants (IOI20_plants) C++17
32 / 100
 857 ms 65792 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
// mn = plant that point to this plant
struct A {
	int mn, idx;
	A operator + (const A& o) const {
		A t;
		if (mn < o.mn) t = *this;
		else t = o;
		return t;
	}
} tree[4 * N], tree1[4 * N];
struct B {
	int mx, idx;
	B operator + (const B& o) const {
		B t;
		if (mx > o.mx) t = *this;
		else t = o;
		return t;
	}
} tree2[4 * N];
// tree -> candidate
// tree1 -> non candidate
int lazy[4 * N], lazy1[4 * N], lv[N];
int jl[20][N], jr[20][N];
int n, k, a[N];
bool ch[N];
vector<int> adj[N];
void build(int now = 1, int l = 0, int r = n - 1) {
	if (l == r) {
		tree[now].mn = 1e9;
		tree1[now].mn = a[l];
		tree2[now].mx = 0;
		tree[now].idx = tree1[now].idx = tree2[now].idx = l;
		return;
	}
	int mid = (l + r) / 2;
	build(2 * now, l, mid), build(2 * now + 1, mid + 1, r);
	tree[now] = tree[2 * now] + tree[2 * now + 1];
	tree1[now] = tree1[2 * now] + tree1[2 * now + 1];
	tree2[now] = tree2[2 * now] + tree2[2 * now + 1];
}
void lzy(int now, int l, int r) {
	tree[now].mn += lazy[now];
	tree1[now].mn += lazy1[now];
	if (l != r) {
		lazy[2 * now] += lazy[now], lazy[2 * now + 1] += lazy[now];
		lazy1[2 * now] += lazy1[now], lazy1[2 * now + 1] += lazy1[now];
	}
	lazy[now] = lazy1[now] = 0;
}
// update arrow
void update(int ql, int qr, int w, int now = 1, int l = 0, int r = n - 1) {
	lzy(now, l, r);
	if (l > qr || r < ql) return;
	if (ql <= l && r <= qr) {
		lazy[now] += w;
		lzy(now, l, r);
		return;
	}
	int mid = (l + r) / 2;
	update(ql, qr, w, 2 * now, l, mid), update(ql, qr, w, 2 * now + 1, mid + 1, r);
	tree[now] = tree[2 * now] + tree[2 * now + 1];
	tree1[now] = tree1[2 * now] + tree1[2 * now + 1];
}
// update r
void update1(int ql, int qr, int w, int now = 1, int l = 0, int r = n - 1) {
	lzy(now, l, r);
	if (l > qr || r < ql) return;
	if (ql <= l && r <= qr) {
		lazy1[now] += w;
		lzy(now, l, r);
		return;
	}
	int mid = (l + r) / 2;
	update1(ql, qr, w, 2 * now, l, mid), update1(ql, qr, w, 2 * now + 1, mid + 1, r);
	tree[now] = tree[2 * now] + tree[2 * now + 1];
	tree1[now] = tree1[2 * now] + tree1[2 * now + 1];
}
void update2(int v, int w, int now = 1, int l = 0, int r = n - 1) {
	if (l == r) {
		tree2[now].mx = w;
		return;
	}
	int mid = (l + r) / 2;
	if (v <= mid) update2(v, w, 2 * now, l, mid);
	else update2(v, w, 2 * now + 1, mid + 1, r);
	tree2[now] = tree2[2 * now] + tree2[2 * now + 1];
}
B query(int ql, int qr, int now = 1, int l = 0, int r = n - 1) {
	if (ql <= l && r <= qr) return tree2[now];
	int mid = (l + r) / 2;
	if (qr <= mid) return query(ql, qr, 2 * now, l, mid);
	if (ql > mid) return query(ql, qr, 2 * now + 1, mid + 1, r);
	return query(ql, qr, 2 * now, l, mid) + query(ql, qr, 2 * now + 1, mid + 1, r);
}
void update_1(int i, int w) {
	int j = i + k - 1;
	if (j >= n) {
		update(i + 1, n - 1, w);
		update(0, j - n, w);
	}
	else update(i + 1, j, w);
}
void update_2(int i) {
	update1(i, i, 1e9);
	update(i, i, -1e9);
}
void update_3(int i, int w) {
	int j = i - k + 1;
	if (j < 0) {
		update1(0, i - 1, w);
		update1(j + n, n - 1, w);
	}
	else update1(j, i - 1, w);
}
void init(int K, vector<int> r) {
	n = r.size();
	k = K;
	for (int i = 0;i < n;i++) a[i] = r[i];
	build();
	for (int i = 0;i < n;i++) {
		if (a[i] == 0) {
			update_1(i, 1); // add arrow
			update_2(i); // transfer to candidate
		}
	}
	stack<int> ord;
	int tot = n;
	while (tot > 0) {
		A now = tree[1];
		int i = now.idx;
		lv[i] = tot--;
		ord.push(i);
		update_1(i, -1); // remove arrow
		update_3(i, -1); // remove previous r
		update(i, i, 1e9);
		A nxt = tree1[1];
		while (nxt.mn == 0) {
			update_1(nxt.idx, 1); // add arrow
			update_2(nxt.idx); // add to candidate
			nxt = tree1[1];
		}
	}
	while (!ord.empty()) {
		int i = ord.top();
		ord.pop();
		// i - k + 1 <- i -> i + k - 1
		// jump left (i - k + 1 <- i)
		{
			int j = i - k + 1;
			B res;
			if (j < 0) res = query(j + n, n - 1) + query(0, i);
			else res = query(j, i);
			if (res.mx == 0) jl[0][i] = i;
			else jl[0][i] = res.idx;
		}
		// jump right (i -> i + k - 1)
		{
			int j = i + k - 1;
			B res;
			if (j >= n) res = query(i, n - 1) + query(0, j - n);
			else res = query(i, j);
			if (res.mx == 0) jr[0][i] = i;
			else jr[0][i] = res.idx;
		}
		update2(i, lv[i]);
	}
	for (int i = 1;i < 20;i++) {
		for (int j = 0;j < n;j++) {
			jl[i][j] = jl[i - 1][jl[i - 1][j]];
			jr[i][j] = jr[i - 1][jr[i - 1][j]];
		}
	}
}
int compare_plants(int x, int y) {
	int ret = (lv[x] > lv[y]) ? 1 : -1;
	if (lv[x] < lv[y]) swap(x, y);
	// jump right
	int idx = x;
	for (int i = 19;i >= 0;i--) {
		if (lv[jr[i][idx]] >= lv[y]) idx = jr[i][idx];
	}
	// check if y in range
	if (idx >= x) {
		if (x <= y && y <= idx) return ret;
	}
	else {
		if (x <= y || y <= idx) return ret;
	}
	// jump left
	idx = x;
	for (int i = 19;i >= 0;i--) {
		if (lv[jl[i][idx]] >= lv[y]) idx = jl[i][idx];
	}
	// check if y in range
	if (idx <= x) {
		if (idx <= y && y <= x) return ret;
	}
	else {
		if (y <= x || idx <= y) return ret;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 43612 KB Output is correct
2 Correct 4 ms 43612 KB Output is correct
3 Correct 4 ms 43608 KB Output is correct
4 Correct 4 ms 43612 KB Output is correct
5 Correct 4 ms 43612 KB Output is correct
6 Correct 55 ms 46328 KB Output is correct
7 Correct 97 ms 47096 KB Output is correct
8 Correct 397 ms 65724 KB Output is correct
9 Correct 415 ms 65684 KB Output is correct
10 Correct 441 ms 65620 KB Output is correct
11 Correct 436 ms 65620 KB Output is correct
12 Correct 417 ms 65664 KB Output is correct
13 Correct 412 ms 65620 KB Output is correct
14 Correct 470 ms 65704 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 43612 KB Output is correct
2 Correct 4 ms 43612 KB Output is correct
3 Correct 4 ms 43612 KB Output is correct
4 Correct 4 ms 43612 KB Output is correct
5 Correct 4 ms 43612 KB Output is correct
6 Correct 8 ms 43612 KB Output is correct
7 Correct 58 ms 46528 KB Output is correct
8 Correct 6 ms 43608 KB Output is correct
9 Correct 7 ms 43612 KB Output is correct
10 Correct 61 ms 46516 KB Output is correct
11 Correct 55 ms 46416 KB Output is correct
12 Correct 66 ms 46656 KB Output is correct
13 Correct 67 ms 46676 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 43612 KB Output is correct
2 Correct 4 ms 43612 KB Output is correct
3 Correct 4 ms 43612 KB Output is correct
4 Correct 4 ms 43612 KB Output is correct
5 Correct 4 ms 43612 KB Output is correct
6 Correct 8 ms 43612 KB Output is correct
7 Correct 58 ms 46528 KB Output is correct
8 Correct 6 ms 43608 KB Output is correct
9 Correct 7 ms 43612 KB Output is correct
10 Correct 61 ms 46516 KB Output is correct
11 Correct 55 ms 46416 KB Output is correct
12 Correct 66 ms 46656 KB Output is correct
13 Correct 67 ms 46676 KB Output is correct
14 Correct 124 ms 47100 KB Output is correct
15 Correct 855 ms 65792 KB Output is correct
16 Correct 127 ms 47216 KB Output is correct
17 Correct 857 ms 65620 KB Output is correct
18 Correct 593 ms 65616 KB Output is correct
19 Correct 601 ms 65728 KB Output is correct
20 Correct 765 ms 65620 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 43612 KB Output is correct
2 Correct 4 ms 43612 KB Output is correct
3 Correct 3 ms 43608 KB Output is correct
4 Correct 4 ms 43612 KB Output is correct
5 Correct 4 ms 43724 KB Output is correct
6 Correct 5 ms 43616 KB Output is correct
7 Correct 15 ms 44124 KB Output is correct
8 Incorrect 14 ms 44376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 43612 KB Output is correct
2 Correct 4 ms 43612 KB Output is correct
3 Correct 4 ms 43608 KB Output is correct
4 Correct 4 ms 43612 KB Output is correct
5 Correct 4 ms 43612 KB Output is correct
6 Correct 55 ms 46328 KB Output is correct
7 Correct 97 ms 47096 KB Output is correct
8 Correct 397 ms 65724 KB Output is correct
9 Correct 415 ms 65684 KB Output is correct
10 Correct 441 ms 65620 KB Output is correct
11 Correct 436 ms 65620 KB Output is correct
12 Correct 417 ms 65664 KB Output is correct
13 Correct 412 ms 65620 KB Output is correct
14 Correct 470 ms 65704 KB Output is correct
15 Correct 4 ms 43612 KB Output is correct
16 Correct 4 ms 43612 KB Output is correct
17 Correct 4 ms 43612 KB Output is correct
18 Correct 4 ms 43612 KB Output is correct
19 Correct 4 ms 43612 KB Output is correct
20 Correct 8 ms 43612 KB Output is correct
21 Correct 58 ms 46528 KB Output is correct
22 Correct 6 ms 43608 KB Output is correct
23 Correct 7 ms 43612 KB Output is correct
24 Correct 61 ms 46516 KB Output is correct
25 Correct 55 ms 46416 KB Output is correct
26 Correct 66 ms 46656 KB Output is correct
27 Correct 67 ms 46676 KB Output is correct
28 Correct 124 ms 47100 KB Output is correct
29 Correct 855 ms 65792 KB Output is correct
30 Correct 127 ms 47216 KB Output is correct
31 Correct 857 ms 65620 KB Output is correct
32 Correct 593 ms 65616 KB Output is correct
33 Correct 601 ms 65728 KB Output is correct
34 Correct 765 ms 65620 KB Output is correct
35 Correct 4 ms 43612 KB Output is correct
36 Correct 4 ms 43612 KB Output is correct
37 Incorrect 60 ms 46380 KB Output isn't correct
38 Halted 0 ms 0 KB -