Submission #1129235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129235		Gervid	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	4 ms	840 KiB

triusis

#include <iostream>
#include <vector>
#include <set>
#include <limits.h>
#include <random>
#include <array>

using namespace std;

mt19937 r;

struct Treap
{
	int prio, dpdata, height, size, dpmin;
	array<Treap*, 2> kids;
	Treap(int _dpdata, int _height)
	{
		height = _height;
		dpdata = _dpdata;
		prio = r();
		size = 1;
		dpmin = dpdata;
		kids = { NULL, NULL };
	}
};

int getsize(Treap* treap)
{
	return treap != NULL ? treap->size : 0;
}

int getdpmin(Treap* treap)
{
	return treap != NULL ? treap->dpmin : INT_MAX;
}

void recalc(Treap* me)
{
	me->dpmin = min(me->dpdata, min(getdpmin(me->kids[0]), getdpmin(me->kids[1])));
	me->size = 1 + getsize(me->kids[0]) + getsize(me->kids[1]);
}

array<Treap*, 2> split(Treap* me, int x)
{
	if (me == NULL) return { NULL, NULL };

	if (x <= getsize(me->kids[0]))
	{
		array<Treap*, 2> res = split(me->kids[0], x);
		me->kids[0] = res[1];
		recalc(me);
		return { res[0], me };
	}
	else
	{
		array<Treap*, 2>res = split(me->kids[1], x - getsize(me->kids[0]) - 1);
		me->kids[1] = res[0];
		recalc(me);
		return { me, res[1] };
	}
}

Treap* merge(Treap* left, Treap* right)
{
	if (left == NULL) return right;
	if (right == NULL) return left;

	if (left->prio < right->prio)
	{
		left->kids[1] = merge(left->kids[1], right);
		recalc(left);
		return left;
	}
	else
	{
		right->kids[0] = merge(left, right->kids[0]);
		recalc(right);
		return right;
	}
}

int findidx(int x, Treap* treap, int index = -1)
{
	if (index == -1) index = getsize(treap->kids[0]);

	if (treap->height == x && (treap->kids[1] == NULL || treap->kids[1]->height != x)) return index;
	if (treap->height <= x)
	{
		if (treap->kids[1] == NULL) return index;
		return findidx(x, treap->kids[1], index + getsize(treap->kids[1]->kids[0]) + 1);
	}
	else
	{
		if (treap->kids[0] == NULL) return index;
		return findidx(x, treap->kids[0], index - getsize(treap->kids[0]->kids[1]) - 1);
 	}
}

int main()
{
	iostream::sync_with_stdio(0);
	cin.tie(0);

	int n, m, i;
	cin >> n >> m;

	vector<int> a(n+1);
	for (i = 1; i <= n; i++) cin >> a[i];
	a[0] = 0;

	vector<Treap> storage = { Treap(n+1, -1) }; //dp value is always offset by i
	storage.reserve(n+2);

	Treap* treap = &storage[storage.size()-1];
	
	multiset<int> heights = { -1 };

	int dis = 0, dpmin = 0, index, smaller_height;
	for (i = n; i >= 0; i--)
	{
		set<int>::iterator it = prev(heights.upper_bound(a[i] + dis));
		smaller_height = *it;
		index = findidx(smaller_height, treap);

		array<Treap*, 2> parts = split(treap, index+1);
		dpmin = parts[0]->dpmin - i - 1;

		storage.push_back(Treap(dpmin + i, a[i] + dis));
		treap = merge(parts[0], merge(&storage[storage.size()-1], parts[1]));
		heights.insert(a[i] + dis);
		dis += m;
	}
	cout << dpmin;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37