Submission #823678

#	Time	Username	Problem	Language	Result	Execution time	Memory
823678		GusterGoose27	Comparing Plants (IOI20_plants)	C++17	44 / 100	708 ms	43788 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+5;
const int inf = 1e9;
int R[MAXN];
int n;

typedef pair<int, int> pii;

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

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	int mn;
	int lz = 0;
	stree(int lp, int rp, bool tp) : lp(lp), rp(rp) {
		if (lp < rp) {
			int md = (lp+rp)/2;
			l = new stree(lp, md, tp);
			r = new stree(md+1, rp, tp);
			mn = min(l->mn, r->mn);
		}
		else mn = tp ? R[lp] : inf;
	}
	void activate(int p) {
		if (lp > p || rp < p) return;
		if (lp == rp) {
			mn = lz;
			return;
		}
		prop();
		l->activate(p);
		r->activate(p);
		mn = min(l->mn, r->mn);
	}
	void set_lz(int p) {
		lz += p;
		mn += p;
	}
	void prop() {
		assert(l);
		l->set_lz(lz);
		r->set_lz(lz);
		lz = 0;
	}
	int find() { // finds a position that is 0
		if (mn > 0) return -1;
		if (lp == rp) return lp;
		prop();
		int lq = l->find();
		if (lq >= 0) return lq;
		int v = r->find();
		assert(v >= 0);
		return v;
	}
	void del(int p) { // can be absorbed into find
		if (lp > p || rp < p) return;
		if (lp == rp) {
			mn = inf;
			return;
		}
		prop();
		l->del(p); r->del(p);
		mn = min(l->mn, r->mn);
	}
	void upd(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			set_lz(v);
			return;
		}
		prop();
		l->upd(lv, rv, v);
		r->upd(lv, rv, v);
		mn = min(l->mn, r->mn);
	}
};

stree *tree[2];

int pos[MAXN];

void init(int k, vector<int> r) {
	n = r.size();
	for (int i = 0; i < n; i++) {
		R[i] = r[i];
	}
	tree[0] = new stree(0, n-1, 0); // 0s to the left
	tree[1] = new stree(0, n-1, 1); // rval
	// for (int i = 0; i < n; i++) {
		// if (r[i] == 0) {
			// tree[0]->upd(i+1, min(n-1, i+k-1), pii(1, 0));
			// if (i+k-1 >= n) tree[0]->upd(0, i+k-1-n, pii(1, 0));
		// }
	// }
	for (int i = 0; i < n; i++) {
		int f1;
		while ((f1 = tree[1]->find()) >= 0) {
			tree[0]->activate(f1);
			tree[1]->del(f1);
			tree[0]->upd(f1+1, min(n-1, f1+k-1), 1);
			if (f1+k-1 >= n) tree[0]->upd(0, f1+k-1-n, 1);
		}
		int v = tree[0]->find();
		assert(v != -1);
		tree[0]->del(v);
		pos[v] = i;
		tree[0]->upd(v+1, min(n-1, v+k-1), -1);
		tree[0]->upd(0, v+k-1-n, -1);
		tree[1]->upd(max(0, v-k+1), v-1, -1);
		if (v-k+1 < 0) tree[1]->upd(n+v-k+1, n-1, -1);
	}
	return;
}

int compare_plants(int x, int y) {
	return 2*(pos[x]<pos[y])-1;
	// if (x != (y+1)%n && y != (x+1)%n) return 0;
	// if (x == (y+1)%n) return 2*(!lt[y])-1;
	// return 2*lt[x]-1;
	// if (x < y) {
	// 	if (pre[y]-pre[x] == y-x) return -1;
	// 	if (pre[x+n]-pre[y] == x+n-y) return 1;
	// 	if (pre[y]-pre[x] == 0) return 1;
	// 	if (pre[x+n]-pre[y] == 0) return -1;
	// 	return 0;
	// // }
	return 0;
}

• 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