제출 #1169975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169975		MateiKing80	식물 비교 (IOI20_plants)	C++20	100 / 100	930 ms	26588 KiB

plants

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

#define low(i) (i << (__builtin_clz(i) - 31 + n_bits)) - (1 << n_bits)
#define high(i) ((i + 1) << (__builtin_clz(i) - 31 + n_bits))-(1 << n_bits) - 1

using namespace std;

vector<int> tallest, shortest;

int n_global;
const int n_bits=20;
const int inf = 1e9;
int arr[1 << (n_bits + 1)], lazyadd[1 << (n_bits + 1)];

struct segtree 
{
	segtree(){}
	void build(vector<int> v) 
	{
		for (int i = 0; i < (1 << n_bits); i++)
			arr[i + (1 << n_bits)] = (i < (int)v.size() ? v[i] : inf);
		for (int i = (1 << n_bits) - 1; i; i --)
			arr[i] = min(arr[2 * i], arr[2 * i + 1]);
		for (int i = 0; i < (1 << (n_bits + 1)); i ++)
			lazyadd[i] = 0;
	}
	int value(int node) 
	{
		arr[node] += lazyadd[node];
		if (node < (1 << n_bits)) 
		{
			lazyadd[2 * node] += lazyadd[node];
			lazyadd[2 * node + 1] += lazyadd[node];
		}
		lazyadd[node] = 0;
		return arr[node];
	}
	void update (int node, int left, int right, int change) 
	{
		if (right >= high(node) && left <= low(node))
			lazyadd[node] += change;
		else if (right < low(node) || left > high(node))
			return;
		else
		{
			update(2 * node, left, right, change);
			update(2 * node + 1, left, right, change);
			arr[node] = min(value(node * 2), value(node * 2 + 1));
		}
	}

	void decr(int left, int right) {update(1, left, right, -1);}

	int find_zero(int node) 
	{
		if (value(node) != 0)
			return -1;
		if (node >= (1<<n_bits))
			return arr[node] == 0 ? node - (1 << n_bits) : -1;
		int x = find_zero(node * 2);
		if (x != -1) 
			return x;
		return find_zero(node * 2 + 1);
	}
};

vector<int> lexi_smallest(int k, vector<int> r) 
{
	segtree s;
	s.build(r);
	vector<int> ret;
	ret.resize(r.size());
	queue<int> stash;
	for (int i = 0; i < (int)r.size(); i ++) 
	{
		int p = s.find_zero(1);
		while (p == -1) 
		{
			s.decr(stash.front(), 2 * n_global - 1);
			p = s.find_zero(1);
			stash.pop();
		}
		ret[p] = i;
		s.update(1, p, p, 1e9);

		s.decr(max(0, p - k + 1), p);
		if (p < k - 1)
			stash.push(p - k + 1 + 2 * n_global);
	}
	return ret;
}

void init(int k, vector<int> r)
{
	n_global = r.size();
	for (int i = 0; i < n_global; i ++)
		r.push_back(r[i]);
	tallest = lexi_smallest(k, r);
	for (int &i: r) 
		i = k - 1 - i;
	shortest = lexi_smallest(k, r);
}

int compare_plants(int x, int y) 
{
	if (x > y) 
		return -compare_plants(y, x);
	if (tallest[x] > tallest[y] || shortest[y] > shortest[x + n_global])
		return -1;
	if (shortest[x] > shortest[y] || tallest[y] > tallest[x+n_global]) 
		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