Submission #457924

#	Time	Username	Problem	Language	Result	Execution time	Memory
457924		ComPhyPark	Comparing Plants (IOI20_plants)	C++14	44 / 100	963 ms	12920 KiB

plants

#include "plants.h"
#include<algorithm>
#include<queue>
using namespace std;
int n;
vector<int>fn, R, st, pp;
bool ifDebug = false;
void mst(int l, int r, int id) {
	if (l == r) {
		st[id] = R[l];
		return;
	}
	int m = (l + r) >> 1;
	mst(l, m, id << 1);
	mst(m + 1, r, id << 1 | 1);
	st[id] = min(st[id << 1], st[id << 1 | 1]);
}
void prop(int l, int r, int id) {
	if (pp[id] && l != r) {
		pp[id << 1] += pp[id];
		st[id << 1] += pp[id];
		pp[id << 1 | 1] += pp[id];
		st[id << 1 | 1] += pp[id];
	}
	pp[id] = 0;
}
void udt(int l, int r, int id, int s, int e, int x) {
	if (l > e || s > r)return;
	if (s <= l && r <= e) {
		st[id] += x;
		pp[id] += x;
		return;
	}
	prop(l, r, id);
	int m = (l + r) >> 1;
	udt(l, m, id << 1, s, e, x);
	udt(m + 1, r, id << 1 | 1, s, e, x);
	st[id] = min(st[id << 1], st[id << 1 | 1]);
}
int qry(int l, int r, int id, int s, int e) {
	if (l > e || s > r)return 999999;
	if (s <= l && r <= e)return st[id];
	prop(l, r, id);
	int m = (l + r) >> 1;
	int rst = min(qry(l, m, id << 1, s, e), qry(m + 1, r, id << 1 | 1, s, e));
	return rst;
}
int fz(int l, int r, int id, int s, int e) {
	if (l > e || s > r)return -1;
	if (l == r)return st[id] ? -1 : l;
	prop(l, r, id);
	int m = (l + r) / 2;
	if (s <= l && r <= e) {
		if (st[2 * id]) {
			return fz(m + 1, r, 2 * id + 1, s, e);
		}
		else {
			return fz(l, m, 2 * id, s, e);
		}
	}
	int a = fz(l, m, 2 * id, s, e);
	return a < 0 ? fz(m + 1, r, 2 * id + 1, s, e) : a;
}
void init(int k, vector<int> r) {
	int i, lfn = r.size(), a, s, e;
	bool ifP;
	queue<int>hb;
	n = r.size();
	R = r;
	st.resize(4 * n);
	pp.resize(4 * n);
	fn.resize(n);
	mst(0, n - 1, 1);
	for (i = 0; i < n; i++) {
		if (r[i] == 0)hb.push(i);
	}
	while (hb.size()) {
		//printf("%d\n", hb.front());
		if (fn[hb.front()]) {
			hb.pop();
			continue;
		}
		ifP = false;
		a = (hb.front() + n - 1) % n;
		if (a > k - 3) {
			if (qry(0, n - 1, 1, a - k + 2, a))ifP = true;
		}
		else {
			if (min(qry(0, n - 1, 1, 0, a), qry(0, n - 1, 1, a + n - k + 2, n - 1)))ifP = true;
		}
		if (ifP) {
			//printf("%d!!!!\n", hb.front());
			a = hb.front();
			fn[a] = lfn--;
			udt(0, n - 1, 1, a, a, n + 1);
			if (a > k - 2) {
				udt(0, n - 1, 1, a - k + 1, a, -1);
			}
			else {
				udt(0, n - 1, 1, 0, a, -1);
				udt(0, n - 1, 1, a + n - k + 1, n - 1, -1);
			}
			s = hb.front() - k + 1;
			e = hb.front() - 1;
			if (s < 0)s += n;
			if (e < 0)e += n;
			//printf("check %d~%d\n", s, e);
			if (s <= e) {
				a = fz(0, n - 1, 1, s, e);
			}
			else {
				a = fz(0, n - 1, 1, s, n - 1);
				if (a < 0) a = fz(0, n - 1, 1, 0, e);
			}
			//printf("push(%d)\n", a);
			if (a >= 0) hb.push(a);
			s = hb.front() + 1;
			e = hb.front() + k - 1;
			s %= n;
			e %= n;
			//printf("check %d~%d\n", s, e);
			if (s <= e) {
				a = fz(0, n - 1, 1, s, e);
			}
			else {
				a = fz(0, n - 1, 1, s, n - 1);
				if (a < 0)a = fz(0, n - 1, 1, 0, e);
			}
			//printf("push(%d)\n", a);
			if (a >= 0)hb.push(a);
		}
		hb.pop();
	}
}
int compare_plants(int x, int y) {
	return fn[x] < fn[y] ? -1 : 1;
}

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