oj.uz

Submission #1050712

# Submission time Handle Problem Language Result Execution time Memory
1050712 2024-08-09T13:07:24 Z thinknoexit Comparing Plants (IOI20_plants) C++17
100 / 100
 852 ms 118260 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
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], __;
int lazy[4 * N], lazy1[4 * N], lv[N];
int jl[19][N], jr[19][N];
ll cl[19][N], cr[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];
}
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;
}
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];
}
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 (l > qr || r < ql) return __;
	if (ql <= l && r <= qr) return tree2[now];
	int mid = (l + r) / 2;
	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);
			update_2(i);
		}
	}
	stack<int> ord;
	for (int _ = 1;_ <= n;_++) {
		A now = tree[1];
		int i = now.idx;
		ord.push(i);
		update_1(i, -1);
		update_3(i, -1);
		update(i, i, 1e9);
		A nxt = tree1[1];
		while (nxt.mn == 0) {
			update_1(nxt.idx, 1);
			update_2(nxt.idx);
			nxt = tree1[1];
		}
	}
	for (int i = 0;i < n;i++) {
		jl[0][i] = jr[0][i] = i;
		cl[0][i] = cr[0][i] = 0;
	}
	int x = 0;
	while (!ord.empty()) {
		int i = ord.top();
		ord.pop();
		{
			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;
				cl[0][i] = (i - res.idx + n) % n;
			}
		}
		{
			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;
				cr[0][i] = (res.idx - i + n) % n;
			}
		}
		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]];
			cl[i][j] = cl[i - 1][j] + cl[i - 1][jl[i - 1][j]];
			jr[i][j] = jr[i - 1][jr[i - 1][j]];
			cr[i][j] = cr[i - 1][j] + cr[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;
	int idx = x;
	ll cnt = 0;
	for (int i = 17;i >= 0;i--) {
		if (lv[jr[i][idx]] >= lv[y]) {
			cnt += cr[i][idx];
			idx = jr[i][idx];
		}
	}
	if (cnt >= n) return ret;
	if (x <= idx) {
		if (x <= y && y <= idx) return ret;
	}
	else {
		if (x <= y || y <= idx) return ret;
	}
	idx = x;
	cnt = 0;
	for (int i = 17;i >= 0;i--) {
		if (lv[jl[i][idx]] >= lv[y]) {
			cnt += cl[i][idx];
			idx = jl[i][idx];
		}
	}
	if (cnt >= n) return ret;
	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 2 ms 23388 KB Output is correct
2 Correct 2 ms 23388 KB Output is correct
3 Correct 2 ms 15192 KB Output is correct
4 Correct 2 ms 17244 KB Output is correct
5 Correct 2 ms 17244 KB Output is correct
6 Correct 42 ms 19916 KB Output is correct
7 Correct 93 ms 32588 KB Output is correct
8 Correct 469 ms 114352 KB Output is correct
9 Correct 465 ms 113952 KB Output is correct
10 Correct 491 ms 114516 KB Output is correct
11 Correct 483 ms 114012 KB Output is correct
12 Correct 496 ms 113820 KB Output is correct
13 Correct 449 ms 117328 KB Output is correct
14 Correct 511 ms 117332 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 21340 KB Output is correct
2 Correct 2 ms 23388 KB Output is correct
3 Correct 1 ms 15196 KB Output is correct
4 Correct 2 ms 23388 KB Output is correct
5 Correct 2 ms 17244 KB Output is correct
6 Correct 5 ms 21852 KB Output is correct
7 Correct 63 ms 28176 KB Output is correct
8 Correct 3 ms 23388 KB Output is correct
9 Correct 5 ms 21852 KB Output is correct
10 Correct 64 ms 28240 KB Output is correct
11 Correct 57 ms 28148 KB Output is correct
12 Correct 65 ms 26192 KB Output is correct
13 Correct 72 ms 26196 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 21340 KB Output is correct
2 Correct 2 ms 23388 KB Output is correct
3 Correct 1 ms 15196 KB Output is correct
4 Correct 2 ms 23388 KB Output is correct
5 Correct 2 ms 17244 KB Output is correct
6 Correct 5 ms 21852 KB Output is correct
7 Correct 63 ms 28176 KB Output is correct
8 Correct 3 ms 23388 KB Output is correct
9 Correct 5 ms 21852 KB Output is correct
10 Correct 64 ms 28240 KB Output is correct
11 Correct 57 ms 28148 KB Output is correct
12 Correct 65 ms 26192 KB Output is correct
13 Correct 72 ms 26196 KB Output is correct
14 Correct 125 ms 34636 KB Output is correct
15 Correct 803 ms 113752 KB Output is correct
16 Correct 121 ms 36692 KB Output is correct
17 Correct 803 ms 117584 KB Output is correct
18 Correct 578 ms 117076 KB Output is correct
19 Correct 652 ms 118260 KB Output is correct
20 Correct 807 ms 117584 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 21340 KB Output is correct
2 Correct 2 ms 21340 KB Output is correct
3 Correct 57 ms 18696 KB Output is correct
4 Correct 575 ms 114304 KB Output is correct
5 Correct 635 ms 117584 KB Output is correct
6 Correct 698 ms 117768 KB Output is correct
7 Correct 748 ms 117380 KB Output is correct
8 Correct 821 ms 118096 KB Output is correct
9 Correct 510 ms 116816 KB Output is correct
10 Correct 543 ms 117464 KB Output is correct
11 Correct 443 ms 117328 KB Output is correct
12 Correct 580 ms 117072 KB Output is correct
13 Correct 589 ms 117472 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 21340 KB Output is correct
2 Correct 2 ms 23388 KB Output is correct
3 Correct 2 ms 15196 KB Output is correct
4 Correct 1 ms 15196 KB Output is correct
5 Correct 2 ms 15196 KB Output is correct
6 Correct 3 ms 17244 KB Output is correct
7 Correct 14 ms 17756 KB Output is correct
8 Correct 12 ms 21988 KB Output is correct
9 Correct 12 ms 24280 KB Output is correct
10 Correct 10 ms 16216 KB Output is correct
11 Correct 12 ms 16220 KB Output is correct
12 Correct 11 ms 18304 KB Output is correct
13 Correct 10 ms 18292 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17244 KB Output is correct
2 Correct 2 ms 23388 KB Output is correct
3 Correct 2 ms 17116 KB Output is correct
4 Correct 2 ms 17244 KB Output is correct
5 Correct 5 ms 17500 KB Output is correct
6 Correct 602 ms 116168 KB Output is correct
7 Correct 666 ms 116168 KB Output is correct
8 Correct 766 ms 116560 KB Output is correct
9 Correct 813 ms 117084 KB Output is correct
10 Correct 541 ms 115936 KB Output is correct
11 Correct 677 ms 116560 KB Output is correct
12 Correct 499 ms 116352 KB Output is correct
13 Correct 609 ms 116560 KB Output is correct
14 Correct 653 ms 116848 KB Output is correct
15 Correct 738 ms 116556 KB Output is correct
16 Correct 509 ms 116532 KB Output is correct
17 Correct 600 ms 116052 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 23388 KB Output is correct
2 Correct 2 ms 23388 KB Output is correct
3 Correct 2 ms 15192 KB Output is correct
4 Correct 2 ms 17244 KB Output is correct
5 Correct 2 ms 17244 KB Output is correct
6 Correct 42 ms 19916 KB Output is correct
7 Correct 93 ms 32588 KB Output is correct
8 Correct 469 ms 114352 KB Output is correct
9 Correct 465 ms 113952 KB Output is correct
10 Correct 491 ms 114516 KB Output is correct
11 Correct 483 ms 114012 KB Output is correct
12 Correct 496 ms 113820 KB Output is correct
13 Correct 449 ms 117328 KB Output is correct
14 Correct 511 ms 117332 KB Output is correct
15 Correct 2 ms 21340 KB Output is correct
16 Correct 2 ms 23388 KB Output is correct
17 Correct 1 ms 15196 KB Output is correct
18 Correct 2 ms 23388 KB Output is correct
19 Correct 2 ms 17244 KB Output is correct
20 Correct 5 ms 21852 KB Output is correct
21 Correct 63 ms 28176 KB Output is correct
22 Correct 3 ms 23388 KB Output is correct
23 Correct 5 ms 21852 KB Output is correct
24 Correct 64 ms 28240 KB Output is correct
25 Correct 57 ms 28148 KB Output is correct
26 Correct 65 ms 26192 KB Output is correct
27 Correct 72 ms 26196 KB Output is correct
28 Correct 125 ms 34636 KB Output is correct
29 Correct 803 ms 113752 KB Output is correct
30 Correct 121 ms 36692 KB Output is correct
31 Correct 803 ms 117584 KB Output is correct
32 Correct 578 ms 117076 KB Output is correct
33 Correct 652 ms 118260 KB Output is correct
34 Correct 807 ms 117584 KB Output is correct
35 Correct 2 ms 21340 KB Output is correct
36 Correct 2 ms 21340 KB Output is correct
37 Correct 57 ms 18696 KB Output is correct
38 Correct 575 ms 114304 KB Output is correct
39 Correct 635 ms 117584 KB Output is correct
40 Correct 698 ms 117768 KB Output is correct
41 Correct 748 ms 117380 KB Output is correct
42 Correct 821 ms 118096 KB Output is correct
43 Correct 510 ms 116816 KB Output is correct
44 Correct 543 ms 117464 KB Output is correct
45 Correct 443 ms 117328 KB Output is correct
46 Correct 580 ms 117072 KB Output is correct
47 Correct 589 ms 117472 KB Output is correct
48 Correct 2 ms 21340 KB Output is correct
49 Correct 2 ms 23388 KB Output is correct
50 Correct 2 ms 15196 KB Output is correct
51 Correct 1 ms 15196 KB Output is correct
52 Correct 2 ms 15196 KB Output is correct
53 Correct 3 ms 17244 KB Output is correct
54 Correct 14 ms 17756 KB Output is correct
55 Correct 12 ms 21988 KB Output is correct
56 Correct 12 ms 24280 KB Output is correct
57 Correct 10 ms 16216 KB Output is correct
58 Correct 12 ms 16220 KB Output is correct
59 Correct 11 ms 18304 KB Output is correct
60 Correct 10 ms 18292 KB Output is correct
61 Correct 56 ms 28500 KB Output is correct
62 Correct 106 ms 32960 KB Output is correct
63 Correct 553 ms 114008 KB Output is correct
64 Correct 611 ms 115540 KB Output is correct
65 Correct 699 ms 114512 KB Output is correct
66 Correct 817 ms 115796 KB Output is correct
67 Correct 852 ms 114768 KB Output is correct
68 Correct 542 ms 115580 KB Output is correct
69 Correct 696 ms 116052 KB Output is correct
70 Correct 527 ms 115316 KB Output is correct
71 Correct 612 ms 115540 KB Output is correct
72 Correct 727 ms 114512 KB Output is correct
73 Correct 741 ms 115796 KB Output is correct
74 Correct 532 ms 114256 KB Output is correct
75 Correct 572 ms 115536 KB Output is correct