oj.uz

답안 #1047342

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1047342 2024-08-07T12:02:28 Z thinknoexit 식물 비교 (IOI20_plants) C++17
32 / 100
 835 ms 59776 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 - 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

# 결과 실행 시간 메모리 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 3 ms 41304 KB Output is correct
6 Correct 46 ms 44296 KB Output is correct
7 Correct 87 ms 44880 KB Output is correct
8 Correct 450 ms 59476 KB Output is correct
9 Correct 437 ms 59444 KB Output is correct
10 Correct 465 ms 59672 KB Output is correct
11 Correct 448 ms 59652 KB Output is correct
12 Correct 419 ms 59776 KB Output is correct
13 Correct 400 ms 59472 KB Output is correct
14 Correct 431 ms 59676 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 41304 KB Output is correct
2 Correct 3 ms 41480 KB Output is correct
3 Correct 3 ms 41304 KB Output is correct
4 Correct 3 ms 41404 KB Output is correct
5 Correct 4 ms 41308 KB Output is correct
6 Correct 7 ms 41564 KB Output is correct
7 Correct 56 ms 44368 KB Output is correct
8 Correct 5 ms 41564 KB Output is correct
9 Correct 8 ms 41408 KB Output is correct
10 Correct 58 ms 44504 KB Output is correct
11 Correct 85 ms 44368 KB Output is correct
12 Correct 63 ms 44560 KB Output is correct
13 Correct 69 ms 44368 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 41304 KB Output is correct
2 Correct 3 ms 41480 KB Output is correct
3 Correct 3 ms 41304 KB Output is correct
4 Correct 3 ms 41404 KB Output is correct
5 Correct 4 ms 41308 KB Output is correct
6 Correct 7 ms 41564 KB Output is correct
7 Correct 56 ms 44368 KB Output is correct
8 Correct 5 ms 41564 KB Output is correct
9 Correct 8 ms 41408 KB Output is correct
10 Correct 58 ms 44504 KB Output is correct
11 Correct 85 ms 44368 KB Output is correct
12 Correct 63 ms 44560 KB Output is correct
13 Correct 69 ms 44368 KB Output is correct
14 Correct 132 ms 45132 KB Output is correct
15 Correct 835 ms 59468 KB Output is correct
16 Correct 132 ms 45068 KB Output is correct
17 Correct 817 ms 59480 KB Output is correct
18 Correct 594 ms 59480 KB Output is correct
19 Correct 647 ms 59472 KB Output is correct
20 Correct 735 ms 59588 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 41308 KB Output is correct
2 Correct 3 ms 41308 KB Output is correct
3 Incorrect 51 ms 44180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 41308 KB Output is correct
2 Correct 4 ms 41304 KB Output is correct
3 Correct 3 ms 41308 KB Output is correct
4 Correct 4 ms 41304 KB Output is correct
5 Correct 4 ms 41308 KB Output is correct
6 Correct 4 ms 41568 KB Output is correct
7 Correct 13 ms 42028 KB Output is correct
8 Incorrect 13 ms 42008 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 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 41516 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 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 3 ms 41304 KB Output is correct
6 Correct 46 ms 44296 KB Output is correct
7 Correct 87 ms 44880 KB Output is correct
8 Correct 450 ms 59476 KB Output is correct
9 Correct 437 ms 59444 KB Output is correct
10 Correct 465 ms 59672 KB Output is correct
11 Correct 448 ms 59652 KB Output is correct
12 Correct 419 ms 59776 KB Output is correct
13 Correct 400 ms 59472 KB Output is correct
14 Correct 431 ms 59676 KB Output is correct
15 Correct 3 ms 41304 KB Output is correct
16 Correct 3 ms 41480 KB Output is correct
17 Correct 3 ms 41304 KB Output is correct
18 Correct 3 ms 41404 KB Output is correct
19 Correct 4 ms 41308 KB Output is correct
20 Correct 7 ms 41564 KB Output is correct
21 Correct 56 ms 44368 KB Output is correct
22 Correct 5 ms 41564 KB Output is correct
23 Correct 8 ms 41408 KB Output is correct
24 Correct 58 ms 44504 KB Output is correct
25 Correct 85 ms 44368 KB Output is correct
26 Correct 63 ms 44560 KB Output is correct
27 Correct 69 ms 44368 KB Output is correct
28 Correct 132 ms 45132 KB Output is correct
29 Correct 835 ms 59468 KB Output is correct
30 Correct 132 ms 45068 KB Output is correct
31 Correct 817 ms 59480 KB Output is correct
32 Correct 594 ms 59480 KB Output is correct
33 Correct 647 ms 59472 KB Output is correct
34 Correct 735 ms 59588 KB Output is correct
35 Correct 4 ms 41308 KB Output is correct
36 Correct 3 ms 41308 KB Output is correct
37 Incorrect 51 ms 44180 KB Output isn't correct
38 Halted 0 ms 0 KB -