Submission #430570

#	Time	Username	Problem	Language	Result	Execution time	Memory
430570		nvmdava	Comparing Plants (IOI20_plants)	C++17	100 / 100	1460 ms	56688 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][20], ri[200005][20];
vector<int> q;
int h[200005];

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

int k;

void init(int k, std::vector<int> v) {
	n = v.size();
	--k;
	::k = k;
	for(auto& x : v)
		x = k - x;
	s.build(1, 0, n - 1, v);
	
	for(auto& x : v)
		x = 0;
	t.build(1, 0, n - 1, v);
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < 20; ++j)
			ri[i][j] = le[i][j] = -1;
	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, now - k, now - 1), s.query(1, 0, n - 1, now - k + n, n - 1));
		
		while(tmp.ff == 0){
			q.push_back(now);
			now = tmp.ss;
			tmp = min(s.query(1, 0, n - 1, now - k, now - 1), s.query(1, 0, n - 1, now - k + n, n - 1));
		}
		
		s.update(1, 0, n - 1, now, now, 800'005);
		s.update(1, 0, n - 1, now - k, now - 1, -1);
		s.update(1, 0, n - 1, now - k + n, n - 1, -1);
		
		h[now] = i;
		
		tmp = min(t.query(1, 0, n - 1, now - k, now - 1), t.query(1, 0, n - 1, now - k + n, n - 1));
		le[now][0] = tmp.ff == 0 ? -1 : tmp.ss;

		tmp = min(t.query(1, 0, n - 1, now + 1, now + k), t.query(1, 0, n - 1, 0, now + k - n));
		ri[now][0] = tmp.ff == 0 ? -1 : tmp.ss;
		for(int i = 0; le[now][i] != -1; ++i){
			le[now][i + 1] = le[le[now][i]][i];
			if(le[now][i + 1] != -1 && cw(le[now][i], le[now][i + 1], now))
				le[now][i + 1] = -1;
		}

		for(int i = 0; ri[now][i] != -1; ++i){
			ri[now][i + 1] = ri[ri[now][i]][i];
			if(ri[now][i + 1] != -1 && cw(now, ri[now][i + 1], ri[now][i]))
				ri[now][i + 1] = -1;
		}
		
		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);
	int ry = y, ly = y;

	for(int i = 19; i >= 0; --i)
		if(ri[ry][i] != -1 && cw(ry, ri[ry][i], x) && x != ry)
			ry = ri[ry][i];

	if(min(abs(ry - x), n - abs(ry - x)) <= k && h[ry] >= h[x])
		return -1;

	for(int i = 19; i >= 0; --i)
		if(le[ly][i] != -1 && cw(x, le[ly][i], ly) && x != ly)
			ly = le[ly][i];

	if(min(abs(ly - x), n - abs(ly - x)) <= k && h[ly] >= h[x])
		return -1;

	return 0;
}

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