oj.uz

Submission #1047388

# Submission time Handle Problem Language Result Execution time Memory
1047388 2024-08-07T12:23:30 Z thinknoexit Comparing Plants (IOI20_plants) C++17
32 / 100
 807 ms 61780 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 if (mx < o.mx) t = o;
		else if (mx == o.mx) {
			if (idx > o.idx) 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];
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) {
	if (i == n - 1) {
		update(0, k - 2, w);
		return;
	}
	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) {
	if (i == 0) {
		update1(n - k + 1, n - 1, w);
		return;
	}
	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;
	}
	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;
		}
		{
			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;
	int idx = x;
	for (int i = 17;i >= 0;i--) {
		if (lv[jr[i][idx]] >= lv[y]) idx = jr[i][idx];
	}
	if (x <= idx) {
		if (x <= y && y <= idx) return ret;
	}
	else {
		if (x <= y || y <= idx) return ret;
	}
	idx = x;
	for (int i = 17;i >= 0;i--) {
		if (lv[jl[i][idx]] >= lv[y]) idx = jl[i][idx];
	}
	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 41308 KB Output is correct
2 Correct 3 ms 41452 KB Output is correct
3 Correct 3 ms 41308 KB Output is correct
4 Correct 3 ms 41308 KB Output is correct
5 Correct 3 ms 41308 KB Output is correct
6 Correct 47 ms 44876 KB Output is correct
7 Correct 105 ms 46160 KB Output is correct
8 Correct 395 ms 61524 KB Output is correct
9 Correct 403 ms 61432 KB Output is correct
10 Correct 396 ms 61268 KB Output is correct
11 Correct 397 ms 61264 KB Output is correct
12 Correct 402 ms 61440 KB Output is correct
13 Correct 405 ms 61264 KB Output is correct
14 Correct 419 ms 61264 KB Output is correct

Subtask #2
14.0 / 14.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 4 ms 41452 KB Output is correct
4 Correct 3 ms 41308 KB Output is correct
5 Correct 3 ms 41308 KB Output is correct
6 Correct 6 ms 41436 KB Output is correct
7 Correct 58 ms 45580 KB Output is correct
8 Correct 5 ms 41564 KB Output is correct
9 Correct 6 ms 41564 KB Output is correct
10 Correct 58 ms 45628 KB Output is correct
11 Correct 56 ms 45576 KB Output is correct
12 Correct 63 ms 45908 KB Output is correct
13 Correct 57 ms 45652 KB Output is correct

Subtask #3
13.0 / 13.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 4 ms 41452 KB Output is correct
4 Correct 3 ms 41308 KB Output is correct
5 Correct 3 ms 41308 KB Output is correct
6 Correct 6 ms 41436 KB Output is correct
7 Correct 58 ms 45580 KB Output is correct
8 Correct 5 ms 41564 KB Output is correct
9 Correct 6 ms 41564 KB Output is correct
10 Correct 58 ms 45628 KB Output is correct
11 Correct 56 ms 45576 KB Output is correct
12 Correct 63 ms 45908 KB Output is correct
13 Correct 57 ms 45652 KB Output is correct
14 Correct 119 ms 46416 KB Output is correct
15 Correct 807 ms 61520 KB Output is correct
16 Correct 125 ms 46416 KB Output is correct
17 Correct 759 ms 61524 KB Output is correct
18 Correct 537 ms 61248 KB Output is correct
19 Correct 576 ms 61780 KB Output is correct
20 Correct 724 ms 61568 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 41308 KB Output is correct
2 Correct 3 ms 41308 KB Output is correct
3 Incorrect 52 ms 45180 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 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 41480 KB Output is correct
5 Correct 4 ms 41308 KB Output is correct
6 Correct 5 ms 41564 KB Output is correct
7 Correct 14 ms 42332 KB Output is correct
8 Incorrect 14 ms 42328 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 4 ms 41408 KB Output is correct
4 Correct 3 ms 41308 KB Output is correct
5 Incorrect 5 ms 41308 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 41308 KB Output is correct
2 Correct 3 ms 41452 KB Output is correct
3 Correct 3 ms 41308 KB Output is correct
4 Correct 3 ms 41308 KB Output is correct
5 Correct 3 ms 41308 KB Output is correct
6 Correct 47 ms 44876 KB Output is correct
7 Correct 105 ms 46160 KB Output is correct
8 Correct 395 ms 61524 KB Output is correct
9 Correct 403 ms 61432 KB Output is correct
10 Correct 396 ms 61268 KB Output is correct
11 Correct 397 ms 61264 KB Output is correct
12 Correct 402 ms 61440 KB Output is correct
13 Correct 405 ms 61264 KB Output is correct
14 Correct 419 ms 61264 KB Output is correct
15 Correct 4 ms 41308 KB Output is correct
16 Correct 3 ms 41308 KB Output is correct
17 Correct 4 ms 41452 KB Output is correct
18 Correct 3 ms 41308 KB Output is correct
19 Correct 3 ms 41308 KB Output is correct
20 Correct 6 ms 41436 KB Output is correct
21 Correct 58 ms 45580 KB Output is correct
22 Correct 5 ms 41564 KB Output is correct
23 Correct 6 ms 41564 KB Output is correct
24 Correct 58 ms 45628 KB Output is correct
25 Correct 56 ms 45576 KB Output is correct
26 Correct 63 ms 45908 KB Output is correct
27 Correct 57 ms 45652 KB Output is correct
28 Correct 119 ms 46416 KB Output is correct
29 Correct 807 ms 61520 KB Output is correct
30 Correct 125 ms 46416 KB Output is correct
31 Correct 759 ms 61524 KB Output is correct
32 Correct 537 ms 61248 KB Output is correct
33 Correct 576 ms 61780 KB Output is correct
34 Correct 724 ms 61568 KB Output is correct
35 Correct 3 ms 41308 KB Output is correct
36 Correct 3 ms 41308 KB Output is correct
37 Incorrect 52 ms 45180 KB Output isn't correct
38 Halted 0 ms 0 KB -