Submission #832526

#	Time	Username	Problem	Language	Result	Execution time	Memory
832526		Johann	Comparing Plants (IOI20_plants)	C++14	0 / 100	1 ms	468 KiB

plants

#include "plants.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

pii operator+(const pii &a, const pii &b)
{
	return {a.first + b.first, a.second + b.second};
}

const int INF = 1 << 30;
int N, K;
vi A;

struct segtree
{
	int size;
	vpii arr;
	vi op;
	void init(vi &R)
	{
		size = 1;
		while (size < sz(R))
			size *= 2;
		arr.assign(2 * size, {0, 0});
		op.assign(2 * size, 0);
		for (int i = 0; i < sz(R); ++i)
			arr[i + size] = {R[i], i};
		for (int i = size - 1; i > 0; --i)
			arr[i] = min(arr[2 * i], arr[2 * i + 1]);
	}
	void propagate(int x)
	{
		if (x < size)
		{
			op[2 * x] += op[x];
			op[2 * x + 1] += op[x];
		}
		arr[x] = arr[x] + make_pair(op[x], 0);
		op[x] = 0;
	}
	void set(int i, int v)
	{
		i += size;
		arr[i] = {v, i - size};
		while ((i >>= 1) > 0)
			arr[i] = min(arr[2 * i], arr[2 * i + 1]);
	}
	void add(int l, int r, int v)
	{
		if (l < 0)
			add(l + N, N, v, 1, 0, size);
		add(max(l, 0), r, v, 1, 0, size);
	}
	void add(int l, int r, int v, int x, int lx, int rx)
	{
		if (l <= lx && rx <= r)
		{
			op[x] += v;
			propagate(x);
			return;
		}
		if (r <= lx || rx <= l)
			return;
		propagate(x);
		int m = (lx + rx) / 2;
		add(l, r, v, 2 * x, lx, m);
		add(l, r, v, 2 * x + 1, m, rx);
		arr[x] = min(arr[2 * x], arr[2 * x + 1]);
	}
	pii query(int l, int r)
	{
		pii left = {INF, -1};
		if (l < 0)
			left = query(l + N, N, 1, 0, size);
		pii right = query(max(l, 0), r, 1, 0, size);
		if (left.first == right.first)
			return left;
		else
			return min(left, right);
	}
	pii query(int l, int r, int x, int lx, int rx)
	{
		propagate(x);
		if (l <= lx && rx <= r)
			return arr[x];
		if (r <= lx || rx <= l)
			return {INF, -1};
		int m = (lx + rx) / 2;
		return min(query(l, r, 2 * x, lx, m), query(l, r, 2 * x + 1, m, rx));
	}
};
segtree seg;

void init(int _K, std::vector<int> r)
{
	K = _K;
	N = sz(r);
	A.assign(N, -1);
	seg.init(r);
	for (int i = N; i > 0; --i)
	{
		pii cand = seg.query(0, N);
		assert(cand.first == 0);
		int idx = seg.query(cand.second - K + 1, cand.second + 1).second;
		assert(idx != -1 && A[idx] == -1);
		A[idx] = i;
		seg.set(idx, INF);
		seg.add(idx - K + 1, idx, -1);
	}
	return;
}

int compare_plants(int x, int y)
{
	return (A[x] > A[y]) ? 1 : -1;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25