oj.uz

답안 #1050663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1050663 2024-08-09T12:15:34 Z thinknoexit 식물 비교 (IOI20_plants) C++17
14 / 100
 4000 ms 63312 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;
	int idx = x;
	while (lv[jr[0][idx]] >= lv[y] && jr[0][idx] != idx) idx = jr[0][idx];
	if (x <= idx) {
		if (x <= y && y <= idx) return ret;
	}
	else {
		if (x <= y || y <= idx) return ret;
	}
	idx = x;
	while (lv[jl[0][idx]] >= lv[y] && jl[0][idx] != idx) idx = jl[0][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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 37212 KB Output is correct
2 Correct 3 ms 37212 KB Output is correct
3 Correct 3 ms 37212 KB Output is correct
4 Correct 4 ms 37212 KB Output is correct
5 Correct 3 ms 37212 KB Output is correct
6 Correct 30 ms 41072 KB Output is correct
7 Correct 105 ms 45392 KB Output is correct
8 Correct 392 ms 62544 KB Output is correct
9 Correct 398 ms 62548 KB Output is correct
10 Correct 641 ms 62420 KB Output is correct
11 Correct 3330 ms 62552 KB Output is correct
12 Execution timed out 4037 ms 62544 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 39256 KB Output is correct
2 Correct 3 ms 37212 KB Output is correct
3 Correct 3 ms 37212 KB Output is correct
4 Correct 3 ms 37356 KB Output is correct
5 Correct 4 ms 37208 KB Output is correct
6 Correct 9 ms 37424 KB Output is correct
7 Correct 686 ms 42216 KB Output is correct
8 Correct 4 ms 37464 KB Output is correct
9 Correct 9 ms 37468 KB Output is correct
10 Correct 684 ms 42308 KB Output is correct
11 Correct 635 ms 42320 KB Output is correct
12 Correct 325 ms 42324 KB Output is correct
13 Correct 857 ms 42224 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 39256 KB Output is correct
2 Correct 3 ms 37212 KB Output is correct
3 Correct 3 ms 37212 KB Output is correct
4 Correct 3 ms 37356 KB Output is correct
5 Correct 4 ms 37208 KB Output is correct
6 Correct 9 ms 37424 KB Output is correct
7 Correct 686 ms 42216 KB Output is correct
8 Correct 4 ms 37464 KB Output is correct
9 Correct 9 ms 37468 KB Output is correct
10 Correct 684 ms 42308 KB Output is correct
11 Correct 635 ms 42320 KB Output is correct
12 Correct 325 ms 42324 KB Output is correct
13 Correct 857 ms 42224 KB Output is correct
14 Correct 3172 ms 27016 KB Output is correct
15 Execution timed out 4057 ms 63312 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 33112 KB Output is correct
2 Correct 3 ms 33116 KB Output is correct
3 Correct 3 ms 33116 KB Output is correct
4 Correct 3 ms 33116 KB Output is correct
5 Correct 3 ms 33236 KB Output is correct
6 Correct 3 ms 33216 KB Output is correct
7 Correct 11 ms 36124 KB Output is correct
8 Incorrect 13 ms 34088 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 35164 KB Output is correct
2 Correct 3 ms 35164 KB Output is correct
3 Correct 3 ms 33116 KB Output is correct
4 Correct 3 ms 33212 KB Output is correct
5 Incorrect 5 ms 33372 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 37212 KB Output is correct
2 Correct 3 ms 37212 KB Output is correct
3 Correct 3 ms 37212 KB Output is correct
4 Correct 4 ms 37212 KB Output is correct
5 Correct 3 ms 37212 KB Output is correct
6 Correct 30 ms 41072 KB Output is correct
7 Correct 105 ms 45392 KB Output is correct
8 Correct 392 ms 62544 KB Output is correct
9 Correct 398 ms 62548 KB Output is correct
10 Correct 641 ms 62420 KB Output is correct
11 Correct 3330 ms 62552 KB Output is correct
12 Execution timed out 4037 ms 62544 KB Time limit exceeded
13 Halted 0 ms 0 KB -