Submission #1129328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129328		Gervid	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	924 ms	18356 KiB

triusis

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

using namespace std;

mt19937 r, t;

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 getvalue(int idx, Treap* treap, int current = -1)
{
	if (current == -1) current = getsize(treap->kids[0]);
	if (idx < current) return getvalue(idx, treap->kids[0], current - getsize(treap->kids[0]->kids[1]) - 1);
	if (idx > current) return getvalue(idx, treap->kids[1], current + getsize(treap->kids[1]->kids[0]) + 1);
	return treap->height;
}

int bsidx(int x, Treap* treap)
{
	int l = 0, r = getsize(treap), m;
	while (l + 1 < r)
	{
		m = (l + r) / 2;
		if (getvalue(m, treap) <= x) l = m;
		else r = m;
	}
	return l;
}

int popcnt(int x)
{
	int ans = 0;
	while (x > 0)
	{
		ans += x & 1;
		x >>= 1;
	}
	return ans;
}
int BruteForce(int n, int m, vector<int> a)
{
	int i, minv = INT_MAX;
	for (int mask = 0; mask < (1<<n); mask++)
	{
		int h = 0, pc = popcnt(mask);
		if (pc >= minv) continue;
		for (i = 0; i < n; i++)
		{
			h += m;
			if (!((mask >> i) & 1))
			{
				if (h < a[i+1]) break;
				h = a[i + 1];
			}
		}
		if (i == n) minv = min(minv, pc);
	}
	return minv;
}

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;

//start:
//	n = 1 + r() % 10, m = r() % 10;
//	a.resize(n + 1);
//	for (i = 1; i <= n; i++) a[i] = r() % 10;

	{
		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 = bsidx(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 << '\n';

		//if (BruteForce(n, m, a) == dpmin) goto start;
		//else
		//{
		//	cout << BruteForce(n, m, a) << '\n';
		//	cout << n << ' ' << m << '\n';
		//	for (i = 1; i < n + 1; i++) cout << a[i] << ' ';
		//}
	}
}

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