Submission #1043635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043635		thinknoexit	Comparing Plants (IOI20_plants)	C++17	0 / 100	4051 ms	4444 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 r, mn, idx;
	A operator + (const A& o) const {
		A t;
		if (mn < o.mn || (mn == o.mn && r < o.r))
			t = *this;
		else
			t = o;
		return t;
	}
} tree[4 * N];
int lazy[4 * N], lazy2[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].r = a[l];
		tree[now].mn = 0;
		tree[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];
}
void lzy(int now, int l, int r) {
	tree[now].mn += lazy[now];
	tree[now].r += lazy2[now];
	if (l != r) {
		lazy[2 * now] += lazy[now], lazy[2 * now + 1] += lazy[now];
		lazy2[2 * now] += lazy2[now], lazy2[2 * now + 1] += lazy2[now];
	}
	lazy[now] = lazy2[now] = 0;
}
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, 2 * now + 1, mid + 1, r);
	tree[now] = tree[2 * now] + tree[2 * now + 1];
}
void update2(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) {
		lazy2[now] += w;
		lzy(now, l, r);
		return;
	}
	int mid = (l + r) / 2;
	update2(ql, qr, w, 2 * now, l, mid), update2(ql, qr, 2 * now + 1, mid + 1, r);
	tree[now] = tree[2 * now] + tree[2 * now + 1];
}
A query(int ql, int qr, int now = 1, int l = 0, int r = n - 1) {
	lzy(now, l, r);
	if (ql <= l && r <= qr) return tree[now];
	int mid = (l + r) / 2;
	if (qr <= mid) return query(ql, qr, 2 * now, l, mid);
	if (ql > mid) return query(ql, qr, 2 * now + 1, mid + 1, r);
	return query(ql, qr, 2 * now, l, mid) + query(ql, qr, 2 * now + 1, mid + 1, r);
}
void update1(int i, int w) { // add arrow
	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 update3(int i, int w) {
	int j = i - k + 1;
	if (j < 0) {
		update2(0, i - 1, w);
		update2(j + n, n - 1, w);
	}
	else {
		update2(j, i - 1, w);
	}
}
A query1(int i) {
	int j = i + k - 1;
	if (j >= n) {
		return query(i + 1, n) + query(0, j - n);
	}
	return query(i + 1, j);
}
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) update1(i, 1), update(i, i, 1e9);
	}
	int tot = 0;
	while (tot != n) {
		A now = tree[1];
		int i = now.idx;
		ord[i] = ++tot;
		update1(i, -1);
		update3(i, -1);
		A nxt = query1(i);
		while (nxt.r == 0 && nxt.mn == 0) {
			update1(nxt.idx, 1), update(nxt.idx, nxt.idx, 1e9);
			nxt = query1(i);
		}
	}
}
int compare_plants(int x, int y) {
	return (ord[x] < ord[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