Submission #1043678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043678		thinknoexit	Comparing Plants (IOI20_plants)	C++17	44 / 100	584 ms	26448 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
// mn = plant that point to this plant
struct A {
	int mn, idx;
	A operator + (const A& o) const {
		A t;
		if (mn < o.mn) t = *this;
		else t = o;
		return t;
	}
} tree[4 * N], tree1[4 * N];
// tree -> candidate
// tree1 -> non candidate
int lazy[4 * N], lazy1[4 * N];
int n, k;
int ord[N], a[N];
void build(int now = 1, int l = 0, int r = n - 1) {
	if (l == r) {
		tree[now].mn = 1e9;
		tree1[now].mn = a[l];
		tree[now].idx = tree1[now].idx = l;
		return;
	}
	int mid = (l + r) / 2;
	build(2 * now, l, mid), build(2 * now + 1, mid + 1, r);
	tree[now] = tree[2 * now] + tree[2 * now + 1];
	tree1[now] = tree1[2 * now] + tree1[2 * now + 1];
}
void lzy(int now, int l, int r) {
	tree[now].mn += lazy[now];
	tree1[now].mn += lazy1[now];
	if (l != r) {
		lazy[2 * now] += lazy[now], lazy[2 * now + 1] += lazy[now];
		lazy1[2 * now] += lazy1[now], lazy1[2 * now + 1] += lazy1[now];
	}
	lazy[now] = lazy1[now] = 0;
}
// update arrow
void update(int ql, int qr, int w, int now = 1, int l = 0, int r = n - 1) {
	lzy(now, l, r);
	if (l > qr || r < ql) return;
	if (ql <= l && r <= qr) {
		lazy[now] += w;
		lzy(now, l, r);
		return;
	}
	int mid = (l + r) / 2;
	update(ql, qr, w, 2 * now, l, mid), update(ql, qr, w, 2 * now + 1, mid + 1, r);
	tree[now] = tree[2 * now] + tree[2 * now + 1];
	tree1[now] = tree1[2 * now] + tree1[2 * now + 1];
}
// update r
void update1(int ql, int qr, int w, int now = 1, int l = 0, int r = n - 1) {
	lzy(now, l, r);
	if (l > qr || r < ql) return;
	if (ql <= l && r <= qr) {
		lazy1[now] += w;
		lzy(now, l, r);
		return;
	}
	int mid = (l + r) / 2;
	update1(ql, qr, w, 2 * now, l, mid), update1(ql, qr, w, 2 * now + 1, mid + 1, r);
	tree[now] = tree[2 * now] + tree[2 * now + 1];
	tree1[now] = tree1[2 * now] + tree1[2 * now + 1];
}
void update_1(int i, int w) {
	int j = i + k - 1;
	if (j >= n) {
		update(i + 1, n - 1, w);
		update(0, j - n, w);
	}
	else update(i + 1, j, w);
}
void update_2(int i) {
	update1(i, i, 1e9);
	update(i, i, -1e9);
}
void update_3(int i, int w) {
	int j = i - k + 1;
	if (j < 0) {
		update1(0, i - 1, w);
		update1(j + n, n - 1, w);
	}
	else update1(j, i - 1, w);
}
void init(int K, vector<int> r) {
	n = r.size();
	k = K;
	for (int i = 0;i < n;i++) a[i] = r[i];
	build();
	for (int i = 0;i < n;i++) {
		if (a[i] == 0) {
			update_1(i, 1); // add arrow
			update_2(i); // transfer to candidate
		}
	}
	int tot = n;
	while (tot) {
		A now = tree[1];
		int i = now.idx;
		ord[i] = tot--;
		update_1(i, -1); // remove arrow
		update_3(i, -1); // remove previous r
		update(i, i, 1e9);
		A nxt = tree1[1];
		while (nxt.mn == 0) {
			update_1(nxt.idx, 1); // add arrow
			update_2(nxt.idx); // add to candidate
			nxt = tree1[1];
		}
	}
}
int compare_plants(int x, int y) {
	return (ord[x] > ord[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