Submission #769066

#	Time	Username	Problem	Language	Result	Execution time	Memory
769066		t6twotwo	Comparing Plants (IOI20_plants)	C++17	14 / 100	4070 ms	14876 KiB

plants

#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 (stderr)

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
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25