oj.uz

Submission #1046350

# Submission time Handle Problem Language Result Execution time Memory
1046350 2024-08-06T13:20:45 Z thinknoexit Comparing Plants (IOI20_plants) C++17
32 / 100
 779 ms 65872 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];
		if (now.mn != 0) break;
		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];
		}
	}
	assert((int)ord.size() == n);
	for (int i = 0;i < n;i++) {
		jl[0][i] = jr[0][i] = i;
	}
	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] = 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] = 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 3 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 50 ms 46420 KB Output is correct
7 Correct 111 ms 47184 KB Output is correct
8 Correct 416 ms 65872 KB Output is correct
9 Correct 387 ms 65688 KB Output is correct
10 Correct 416 ms 65616 KB Output is correct
11 Correct 384 ms 65620 KB Output is correct
12 Correct 399 ms 65748 KB Output is correct
13 Correct 382 ms 65720 KB Output is correct
14 Correct 438 ms 65616 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 3 ms 43704 KB Output is correct
4 Correct 4 ms 43612 KB Output is correct
5 Correct 4 ms 43612 KB Output is correct
6 Correct 6 ms 43772 KB Output is correct
7 Correct 67 ms 46724 KB Output is correct
8 Correct 5 ms 43612 KB Output is correct
9 Correct 6 ms 43808 KB Output is correct
10 Correct 61 ms 46508 KB Output is correct
11 Correct 60 ms 46420 KB Output is correct
12 Correct 71 ms 46784 KB Output is correct
13 Correct 57 ms 46604 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 3 ms 43704 KB Output is correct
4 Correct 4 ms 43612 KB Output is correct
5 Correct 4 ms 43612 KB Output is correct
6 Correct 6 ms 43772 KB Output is correct
7 Correct 67 ms 46724 KB Output is correct
8 Correct 5 ms 43612 KB Output is correct
9 Correct 6 ms 43808 KB Output is correct
10 Correct 61 ms 46508 KB Output is correct
11 Correct 60 ms 46420 KB Output is correct
12 Correct 71 ms 46784 KB Output is correct
13 Correct 57 ms 46604 KB Output is correct
14 Correct 127 ms 47104 KB Output is correct
15 Correct 779 ms 65592 KB Output is correct
16 Correct 122 ms 47184 KB Output is correct
17 Correct 766 ms 65728 KB Output is correct
18 Correct 529 ms 65784 KB Output is correct
19 Correct 670 ms 65620 KB Output is correct
20 Correct 723 ms 65616 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 43608 KB Output is correct
2 Correct 3 ms 43660 KB Output is correct
3 Incorrect 59 ms 46516 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 43608 KB Output is correct
2 Correct 3 ms 43612 KB Output is correct
3 Correct 4 ms 43612 KB Output is correct
4 Correct 5 ms 43672 KB Output is correct
5 Correct 4 ms 43612 KB Output is correct
6 Correct 5 ms 43612 KB Output is correct
7 Correct 14 ms 44188 KB Output is correct
8 Incorrect 14 ms 44380 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 43612 KB Output is correct
2 Correct 4 ms 43864 KB Output is correct
3 Correct 5 ms 43612 KB Output is correct
4 Correct 3 ms 43612 KB Output is correct
5 Incorrect 6 ms 43740 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 3 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 50 ms 46420 KB Output is correct
7 Correct 111 ms 47184 KB Output is correct
8 Correct 416 ms 65872 KB Output is correct
9 Correct 387 ms 65688 KB Output is correct
10 Correct 416 ms 65616 KB Output is correct
11 Correct 384 ms 65620 KB Output is correct
12 Correct 399 ms 65748 KB Output is correct
13 Correct 382 ms 65720 KB Output is correct
14 Correct 438 ms 65616 KB Output is correct
15 Correct 4 ms 43612 KB Output is correct
16 Correct 4 ms 43612 KB Output is correct
17 Correct 3 ms 43704 KB Output is correct
18 Correct 4 ms 43612 KB Output is correct
19 Correct 4 ms 43612 KB Output is correct
20 Correct 6 ms 43772 KB Output is correct
21 Correct 67 ms 46724 KB Output is correct
22 Correct 5 ms 43612 KB Output is correct
23 Correct 6 ms 43808 KB Output is correct
24 Correct 61 ms 46508 KB Output is correct
25 Correct 60 ms 46420 KB Output is correct
26 Correct 71 ms 46784 KB Output is correct
27 Correct 57 ms 46604 KB Output is correct
28 Correct 127 ms 47104 KB Output is correct
29 Correct 779 ms 65592 KB Output is correct
30 Correct 122 ms 47184 KB Output is correct
31 Correct 766 ms 65728 KB Output is correct
32 Correct 529 ms 65784 KB Output is correct
33 Correct 670 ms 65620 KB Output is correct
34 Correct 723 ms 65616 KB Output is correct
35 Correct 4 ms 43608 KB Output is correct
36 Correct 3 ms 43660 KB Output is correct
37 Incorrect 59 ms 46516 KB Output isn't correct
38 Halted 0 ms 0 KB -