oj.uz

Submission #769066

# Submission time Handle Problem Language Result Execution time Memory
769066 2023-06-29T06:40:23 Z t6twotwo Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 14876 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, K;
vector<int> R, A, pfs;
void init(int k, std::vector<int> r) {
	K = k, R = r; N = R.size();
	A.resize(N, -1);
	if (K == 2) {
		pfs.resize(N + 1);
		for (int i = 0; i < N; i++) {
			pfs[i + 1] = pfs[i] + R[i];
		}
		return;
	}
	int M = 2 << __lg(N - 1);
	vector<int> st(2 * M - 1), lazy(2 * M - 1);
	auto push = [&](int p) {
		st[p * 2 + 1] += lazy[p];
		st[p * 2 + 2] += lazy[p];
		lazy[p * 2 + 1] += lazy[p];
		lazy[p * 2 + 2] += lazy[p];
		lazy[p] = 0;
	};
	auto pull = [&](int p) {
		st[p] = max(st[p * 2 + 1], st[p * 2 + 2]);
	};
	for (int i = 0; i < N; i++) {
		st[i + M - 1] = R[i];
	}
	for (int i = M - 2; i >= 0; i--) {
		pull(i);
	}
	auto modify = [&](auto f, int p, int l, int r, int x, int v) -> void {
		if (r - l == 1) {
			st[p] = v;
			return;
		}
		int m = (l + r + 1) / 2;
		push(p);
		if (x < m) {
			f(f, p * 2 + 1, l, m, x, v);
		} else {
			f(f, p * 2 + 2, m, r, x, v);
		}
		pull(p);
	};
	auto update = [&](auto f, int p, int l, int r, int L, int R) -> void {
		if (R <= l || r <= L) {
			return;
		}
		if (L <= l && r <= R) {
			st[p]++;
			lazy[p]++;
			return;
		}
		int m = (l + r + 1) / 2;
		push(p);
		f(f, p * 2 + 1, l, m, L, R);
		f(f, p * 2 + 2, m, r, L, R);
		pull(p);
	};
	auto find = [&](auto f, int p, int l, int r) {
		if (r - l == 1) {
			return l;
		}
		int m = (l + r + 1) / 2;
		push(p);
		if (st[p * 2 + 1] == K - 1) {
			return f(f, p * 2 + 1, l, m);
		} else {
			return f(f, p * 2 + 2, m, r);
		}
	};
	for (int i = 0; i < N; i++) {
		vector<int> v;
		while (st[0] == K - 1) {
			int x = find(find, 0, 0, M);
			v.push_back(x);
			modify(modify, 0, 0, M, x, -1e9);
		}
		int m = v.size(), p;
		if (m == 1 || N - v[m - 1] + v[0] >= K) {
			p = v[0];
		} else {
			for (int j = 0; j + 1 < m; j++) {
				if (v[j + 1] - v[j] >= K) {
					p = v[j + 1];
				}
			}
		}
		A[p] = i;
		R[p] = -1e9;
		for (int x : v) {
			if (x != p) {
				modify(modify, 0, 0, M, x, K - 1);
			}
		}
		if (p > 0) {
			update(update, 0, 0, M, max(0, p - (K - 1)), p);
		}
		if (p - (K - 1) < 0) {
			update(update, 0, 0, M, N + p - (K - 1), N);
		}
	}
}
 
int compare_plants(int x, int y) {
	if (K == 2) {
		if (pfs[y] - pfs[x] == 0) {
			return 1;
		}
		if (pfs[y] - pfs[x] == y - x) {
			return -1;
		}
		if (pfs[N] - pfs[y] + pfs[x] == 0) {
			return -1;
		}
		if (pfs[N] - pfs[y] + pfs[x] == N - y + x) {
			return 1;
		}
	}
	return A[x] > A[y] ? 1 : -1;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:93:6: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |   A[p] = i;
      |      ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 8 ms 212 KB Output is correct
4 Incorrect 1 ms 212 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 1 ms 296 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 43 ms 5220 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 43 ms 5220 KB Output is correct
11 Correct 41 ms 5084 KB Output is correct
12 Correct 3101 ms 5256 KB Output is correct
13 Correct 48 ms 5328 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 43 ms 5220 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 43 ms 5220 KB Output is correct
11 Correct 41 ms 5084 KB Output is correct
12 Correct 3101 ms 5256 KB Output is correct
13 Correct 48 ms 5328 KB Output is correct
14 Correct 67 ms 5664 KB Output is correct
15 Correct 371 ms 12236 KB Output is correct
16 Correct 71 ms 5704 KB Output is correct
17 Correct 394 ms 13624 KB Output is correct
18 Correct 233 ms 13204 KB Output is correct
19 Execution timed out 4035 ms 14876 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 144 ms 4708 KB Output is correct
4 Execution timed out 4070 ms 12232 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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