oj.uz

Submission #1047219

# Submission time Handle Problem Language Result Execution time Memory
1047219 2024-08-07T10:55:30 Z thinknoexit Comparing Plants (IOI20_plants) C++17
32 / 100
 824 ms 63372 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() : mx(-1), idx(-1) {}
	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[19][N], jr[19][N];
int n, k, a[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];
		tree[now].idx = tree1[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].idx = v;
		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;
	for (int _ = 1;_ <= n;_++) {
		A now = tree[1];
		int i = now.idx;
		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];
		}
	}
	for (int i = 0;i < n;i++) {
		jl[0][i] = jr[0][i] = i;
	}
	int x = 0;
	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 != -1) 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 != -1) jr[0][i] = res.idx;
		}
		lv[i] = ++x;
		update2(i, lv[i]);
	}
	for (int i = 1;i < 18;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 = 1;
	if (lv[x] < lv[y]) swap(x, y), ret = -1;
	// jump right
	int idx = x;
	for (int i = 17;i >= 0;i--) {
		if (lv[jr[i][idx]] >= lv[y]) idx = jr[i][idx];
	}
	// check if y in range
	if (x <= idx) {
		if (x <= y && y <= idx) return ret;
	}
	else {
		if (x <= y || y <= idx) return ret;
	}
	// jump left
	idx = x;
	for (int i = 17;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 (idx <= y || y <= x) return ret;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 41560 KB Output is correct
2 Correct 3 ms 41304 KB Output is correct
3 Correct 3 ms 41308 KB Output is correct
4 Correct 4 ms 41396 KB Output is correct
5 Correct 3 ms 41308 KB Output is correct
6 Correct 47 ms 45316 KB Output is correct
7 Correct 89 ms 47188 KB Output is correct
8 Correct 382 ms 62548 KB Output is correct
9 Correct 434 ms 62528 KB Output is correct
10 Correct 391 ms 62544 KB Output is correct
11 Correct 380 ms 62472 KB Output is correct
12 Correct 420 ms 62488 KB Output is correct
13 Correct 379 ms 62548 KB Output is correct
14 Correct 441 ms 62464 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 41304 KB Output is correct
2 Correct 4 ms 41308 KB Output is correct
3 Correct 3 ms 41428 KB Output is correct
4 Correct 3 ms 41308 KB Output is correct
5 Correct 3 ms 41308 KB Output is correct
6 Correct 7 ms 41564 KB Output is correct
7 Correct 57 ms 46352 KB Output is correct
8 Correct 5 ms 41560 KB Output is correct
9 Correct 7 ms 41560 KB Output is correct
10 Correct 58 ms 46412 KB Output is correct
11 Correct 52 ms 46164 KB Output is correct
12 Correct 67 ms 46400 KB Output is correct
13 Correct 55 ms 46400 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 41304 KB Output is correct
2 Correct 4 ms 41308 KB Output is correct
3 Correct 3 ms 41428 KB Output is correct
4 Correct 3 ms 41308 KB Output is correct
5 Correct 3 ms 41308 KB Output is correct
6 Correct 7 ms 41564 KB Output is correct
7 Correct 57 ms 46352 KB Output is correct
8 Correct 5 ms 41560 KB Output is correct
9 Correct 7 ms 41560 KB Output is correct
10 Correct 58 ms 46412 KB Output is correct
11 Correct 52 ms 46164 KB Output is correct
12 Correct 67 ms 46400 KB Output is correct
13 Correct 55 ms 46400 KB Output is correct
14 Correct 119 ms 47188 KB Output is correct
15 Correct 824 ms 63372 KB Output is correct
16 Correct 122 ms 47188 KB Output is correct
17 Correct 743 ms 63340 KB Output is correct
18 Correct 573 ms 62932 KB Output is correct
19 Correct 570 ms 63312 KB Output is correct
20 Correct 717 ms 63316 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 41304 KB Output is correct
2 Correct 3 ms 41308 KB Output is correct
3 Correct 4 ms 41308 KB Output is correct
4 Correct 3 ms 41308 KB Output is correct
5 Correct 4 ms 41488 KB Output is correct
6 Correct 5 ms 41508 KB Output is correct
7 Correct 14 ms 42332 KB Output is correct
8 Incorrect 13 ms 42340 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 41308 KB Output is correct
2 Correct 3 ms 41308 KB Output is correct
3 Correct 3 ms 41308 KB Output is correct
4 Correct 3 ms 41308 KB Output is correct
5 Incorrect 6 ms 41560 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 41560 KB Output is correct
2 Correct 3 ms 41304 KB Output is correct
3 Correct 3 ms 41308 KB Output is correct
4 Correct 4 ms 41396 KB Output is correct
5 Correct 3 ms 41308 KB Output is correct
6 Correct 47 ms 45316 KB Output is correct
7 Correct 89 ms 47188 KB Output is correct
8 Correct 382 ms 62548 KB Output is correct
9 Correct 434 ms 62528 KB Output is correct
10 Correct 391 ms 62544 KB Output is correct
11 Correct 380 ms 62472 KB Output is correct
12 Correct 420 ms 62488 KB Output is correct
13 Correct 379 ms 62548 KB Output is correct
14 Correct 441 ms 62464 KB Output is correct
15 Correct 3 ms 41304 KB Output is correct
16 Correct 4 ms 41308 KB Output is correct
17 Correct 3 ms 41428 KB Output is correct
18 Correct 3 ms 41308 KB Output is correct
19 Correct 3 ms 41308 KB Output is correct
20 Correct 7 ms 41564 KB Output is correct
21 Correct 57 ms 46352 KB Output is correct
22 Correct 5 ms 41560 KB Output is correct
23 Correct 7 ms 41560 KB Output is correct
24 Correct 58 ms 46412 KB Output is correct
25 Correct 52 ms 46164 KB Output is correct
26 Correct 67 ms 46400 KB Output is correct
27 Correct 55 ms 46400 KB Output is correct
28 Correct 119 ms 47188 KB Output is correct
29 Correct 824 ms 63372 KB Output is correct
30 Correct 122 ms 47188 KB Output is correct
31 Correct 743 ms 63340 KB Output is correct
32 Correct 573 ms 62932 KB Output is correct
33 Correct 570 ms 63312 KB Output is correct
34 Correct 717 ms 63316 KB Output is correct
35 Correct 3 ms 41304 KB Output is correct
36 Correct 4 ms 41304 KB Output is correct
37 Incorrect 57 ms 46100 KB Output isn't correct
38 Halted 0 ms 0 KB -