oj.uz

Submission #1050655

# Submission time Handle Problem Language Result Execution time Memory
1050655 2024-08-09T12:11:51 Z thinknoexit Comparing Plants (IOI20_plants) C++17
44 / 100
 763 ms 62808 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];
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;
	}
	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;
	return ret;
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31064 KB Output is correct
2 Correct 2 ms 29276 KB Output is correct
3 Correct 2 ms 31068 KB Output is correct
4 Incorrect 3 ms 31180 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29276 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 2 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 29276 KB Output is correct
6 Correct 5 ms 31324 KB Output is correct
7 Correct 48 ms 36352 KB Output is correct
8 Correct 3 ms 31328 KB Output is correct
9 Correct 5 ms 31356 KB Output is correct
10 Correct 40 ms 36176 KB Output is correct
11 Correct 36 ms 36180 KB Output is correct
12 Correct 40 ms 36436 KB Output is correct
13 Correct 41 ms 34388 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29276 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 2 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 29276 KB Output is correct
6 Correct 5 ms 31324 KB Output is correct
7 Correct 48 ms 36352 KB Output is correct
8 Correct 3 ms 31328 KB Output is correct
9 Correct 5 ms 31356 KB Output is correct
10 Correct 40 ms 36176 KB Output is correct
11 Correct 36 ms 36180 KB Output is correct
12 Correct 40 ms 36436 KB Output is correct
13 Correct 41 ms 34388 KB Output is correct
14 Correct 83 ms 36132 KB Output is correct
15 Correct 706 ms 62808 KB Output is correct
16 Correct 84 ms 37232 KB Output is correct
17 Correct 702 ms 61488 KB Output is correct
18 Correct 502 ms 59864 KB Output is correct
19 Correct 500 ms 59984 KB Output is correct
20 Correct 737 ms 60932 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33116 KB Output is correct
2 Correct 4 ms 35164 KB Output is correct
3 Correct 32 ms 36108 KB Output is correct
4 Correct 492 ms 61304 KB Output is correct
5 Correct 533 ms 61708 KB Output is correct
6 Correct 642 ms 60812 KB Output is correct
7 Correct 676 ms 61044 KB Output is correct
8 Correct 763 ms 61044 KB Output is correct
9 Correct 486 ms 61340 KB Output is correct
10 Correct 476 ms 61380 KB Output is correct
11 Correct 378 ms 61368 KB Output is correct
12 Correct 423 ms 59776 KB Output is correct
13 Correct 513 ms 59680 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31064 KB Output is correct
2 Correct 2 ms 29276 KB Output is correct
3 Correct 2 ms 31068 KB Output is correct
4 Incorrect 3 ms 31180 KB Output isn't correct
5 Halted 0 ms 0 KB -