Submission #1020105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020105		j_vdd16	Comparing Plants (IOI20_plants)	C++17	14 / 100	4098 ms	9616 KiB

plants

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

typedef uint64_t u64;
typedef int64_t i64;

int k;
struct SegTree {
	const ii id = { INT_MAX, 0 };
	vii tree;
	vi lazySub;
	int n, N;

	SegTree(vi v) {
		n = v.size();
		N = 1;
		while (N < n)
			N *= 2;

		tree.resize(2 * N, id);
		lazySub.resize(2 * N, 0);
		loop(i, n)
			tree[N + i] = { v[i], i };

		for (int i = N - 1; i >= 1; i--)
			tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
	}

	ii merge(ii a, ii b) {
		if (a.first < b.first)
			return a;

		if (b.first < a.first || b.second - a.second >= k)
			return b;

		return a;
	}

	void rangeSub(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
		if (tr == -1)
			tr = N;

		if (tl >= l && tr <= r)
			lazySub[i] = v;

		if (tl >= r || tr <= l)
			return;

		int tm = (tl + tr) / 2;
		range(l, r, i * 2, tl, tm);
		range(l, r, i * 2 + 1, tm, tr);
	}
	ii range(int l, int r, int i = 1, int tl = 0, int tr = -1) {
		if (tr == -1)
			tr = N;

		tree[i].first -= lazySub[i];
		if (tr - tl > 1)
		{
			lazySub[2 * i] = lazySub[i];
			lazySub[2 * i + 1] = lazySub[i];
		}
		lazySub[i] = 0;

		if (tl >= l && tr <= r)
			return tree[i];

		if (tl >= r || tr <= l)
			return id;

		int tm = (tl + tr) / 2;
		return merge(range(l, r, i * 2, tl, tm), range(l, r, i * 2 + 1, tm, tr));
	}
};

int n;
vi r;

vi perm;
void init(int _k, vi _r)
{
	n = _r.size();
	k = _k;
	r = _r;
	perm.assign(n, 0);

	int idx = n;
	vb vis(n);
	while (idx > 0)
	{
		vi lowest;
		int count = 0;
		for (int i = 1; i < k; i++)
			count += vis[i];

		loop(i, n)
		{
			if (r[i] == count && !vis[i])
				lowest.push_back(i);

			count -= vis[(i + 1) % n];
			count += vis[(i + k) % n];
		}

		int n2 = lowest.size();
		int low = lowest[0];
		loop(i, n2 - 1)
		{
			if (lowest[i + 1] - lowest[i] >= k)
			{
				low = lowest[i + 1];
				break;
			}
		}

		vis[low] = true;
		perm[low] = idx--;
	}
}

int compare_plants(int x, int y)
{
	if (perm[x] < perm[y])
		return -1;

	if (perm[x] > perm[y])
		return 1;

	return 0;
}

• 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