Submission #428910

#	Time	Username	Problem	Language	Result	Execution time	Memory
428910		nvmdava	Comparing Plants (IOI20_plants)	C++17	0 / 100	106 ms	15888 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
int n;

struct Segtree{
	pair<int, int> mn[800005];
	int lz[800005];
	void push(int id, int l, int r){
		mn[id].ff += lz[id];
		if(l != r){
			lz[id << 1] += lz[id];
			lz[id << 1 | 1] += lz[id];
		}
		lz[id] = 0;
	}

	void build(int id, int l, int r, vector<int>& v){
		if(l == r){
			mn[id] = {v[l], l};
			return;
		}
		int m = (l + r) >> 1;
		build(id << 1, l, m, v);
		build(id << 1 | 1, m + 1, r, v);

		mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
	}

	void update(int id, int l, int r, int L, int R, int x){
		if(L <= l && r <= R){
			lz[id] += x;
			push(id, l, r);
			return;
		}
		push(id, l, r);
		if(l > R || r < L) return;
		int m = (l + r) >> 1;
		update(id << 1, l, m, L, R, x);
		update(id << 1 | 1, m + 1, r, L, R, x);
		mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
	}

	pair<int, int> query(int id, int l, int r, int L, int R){
		push(id, l, r);
		if(l > R || r < L)
			return {1'000'000, 1};
		if(L <= l && r <= R)
			return mn[id];
		int m = (l + r) >> 1;
		return min(query(id << 1, l, m, L, R), query(id << 1 | 1, m + 1, r, L, R));
	}
} s, t;

int le[200005], ri[200005];
vector<int> q;
int h[200005];

bool circle(int x, int y, int z){
	if(x == z) return 0;
	if(x <= y && y <= z)
		return 1;
	if(z <= x && x <= y)
		return 1;
	if(y <= z && z <= x)
		return 1;
	return 0;
}

void init(int k, std::vector<int> v) {
	n = v.size();

	for(auto& x : v)
		x = k - 1 - x;
	s.build(1, 0, n - 1, v);
	
	for(auto& x : v)
		x = 0;
	t.build(1, 0, n - 1, v);
	
	for(int i = 1; i <= n; ++i){
		int now;
		if(q.empty())
			now = s.query(1, 0, n - 1, 0, n - 1).ss;
		else {
			now = q.back();
			q.pop_back();
		}

		pair<int, int> tmp = min(s.query(1, 0, n - 1, max(0, now - k + 1), now - 1), s.query(1, 0, n - 1, now - k + 1 + n, n - 1));
		
		while(tmp.ff == 0){
			q.push_back(now);
			now = tmp.ss;
			tmp = min(s.query(1, 0, n - 1, now - k + 1, now - 1), s.query(1, 0, n - 1, now - k + 1 + n, n - 1));
		}
		
		s.update(1, 0, n - 1, now, now, 800'005);
		s.update(1, 0, n - 1, now - k + 1, now - 1, -1);
		s.update(1, 0, n - 1, now - k + 1 + n, n - 1, -1);
		
		h[now] = i;
		
		tmp = min(t.query(1, 0, n - 1, now - k + 1, now - 1), t.query(1, 0, n - 1, now - k + 1 + n, n - 1));
		le[now] = tmp.ff == 0 ? now : circle(le[tmp.ss], now, tmp.ss) ? (now + 1) % n : le[tmp.ss];

		tmp = min(t.query(1, 0, n - 1, now - k + 1, now - 1), t.query(1, 0, n - 1, now - k + 1 + n, n - 1));
		ri[now] = tmp.ff == 0 ? now : circle(tmp.ss, now, ri[tmp.ss]) ? (n - 1 + now) % n : ri[tmp.ss];

		t.update(1, 0, n - 1, now, now, -i);
	}
}

int compare_plants(int x, int y) {
	if(h[x] > h[y]) return -compare_plants(y, x);

	if(circle(y, x, ri[y]) || circle(le[y], x, y))
		return -1;
	return 0;
}

• 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