oj.uz

Submission #1047331

# Submission time Handle Problem Language Result Execution time Memory
1047331 2024-08-07T11:58:26 Z thinknoexit Comparing Plants (IOI20_plants) C++17
0 / 100
 425 ms 59828 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];
	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;
}
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 - 1, 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
0 / 5.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 Correct 4 ms 41472 KB Output is correct
6 Correct 46 ms 44112 KB Output is correct
7 Correct 90 ms 45112 KB Output is correct
8 Correct 398 ms 59508 KB Output is correct
9 Correct 425 ms 59476 KB Output is correct
10 Correct 407 ms 59476 KB Output is correct
11 Correct 392 ms 59472 KB Output is correct
12 Correct 398 ms 59828 KB Output is correct
13 Incorrect 400 ms 59472 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

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 51 ms 44172 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 4 ms 41480 KB Output is correct
3 Correct 4 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 5 ms 41564 KB Output is correct
7 Correct 14 ms 42076 KB Output is correct
8 Incorrect 12 ms 41956 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 41484 KB Output is correct
3 Correct 3 ms 41308 KB Output is correct
4 Correct 3 ms 41456 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 41308 KB Output is correct
3 Correct 3 ms 41308 KB Output is correct
4 Correct 3 ms 41308 KB Output is correct
5 Correct 4 ms 41472 KB Output is correct
6 Correct 46 ms 44112 KB Output is correct
7 Correct 90 ms 45112 KB Output is correct
8 Correct 398 ms 59508 KB Output is correct
9 Correct 425 ms 59476 KB Output is correct
10 Correct 407 ms 59476 KB Output is correct
11 Correct 392 ms 59472 KB Output is correct
12 Correct 398 ms 59828 KB Output is correct
13 Incorrect 400 ms 59472 KB Output isn't correct
14 Halted 0 ms 0 KB -