Submission #55017

#	Time	Username	Problem	Language	Result	Execution time	Memory
55017		radoslav11	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	2766 ms	149456 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"
//#include "Lgrader.cpp"

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int inf = (int)2e9 + 42;

random_device rd;
mt19937 mt(rd());

struct node
{
	int sum, val, sz, prior; 
	node *l, *r, *par, *pp;
	node() { l = r = par = pp = nullptr; sum = val = sz = prior = 0; }
	node(int v) { l = r = par = pp = nullptr; sum = val = v; sz = 1; prior = mt(); }
};

using pnode = node*;

pnode get_l(pnode t) { while(t->l) t = t->l; return t; }
pnode get_r(pnode t) { while(t->r) t = t->r; return t; }
pnode get_par(pnode t) { while(t->par) t = t->par; return t; }

inline int size(pnode t) { return t ? t->sz : 0; }
inline int sum(pnode t) { return t ? t->sum : 0; }

void pull(pnode &t)
{
	if(!t) return;

	t->sz = size(t->l) + size(t->r) + 1;
	t->sum = t->val + sum(t->l) + sum(t->r);
	t->par = nullptr;

	if(t->l) t->l->par = t;
	if(t->r) t->r->par = t;

	if(t->l && t->l->pp) t->pp = t->l->pp, t->l->pp = nullptr;
	if(t->r && t->r->pp) t->pp = t->r->pp, t->r->pp = nullptr;
}

void merge(pnode &t, pnode l, pnode r)
{
	if(!l) { t = r; pull(t); return; }
	if(!r) { t = l; pull(t); return; }

	if(l->prior > r->prior)
		merge(l->r, l->r, r), t = l;
	else
		merge(r->l, l, r->l), t = r;

	pull(t);
}

void split(pnode t, pnode &l, pnode &r, int k, int add = 0)
{
	if(!t) { l = nullptr; r = nullptr; return; }

	int idx = add + size(t->l);
	if(idx <= k)
		split(t->r, t->r, r, k, idx + 1), l = t;
	else
		split(t->l, l, t->l, k, add), r = t;

	pull(t);
}

pnode remove_left(pnode u)
{
	int pos = size(u->l);
	pnode root = u;

	while(root->par)
	{
		if(root->par->r == root) pos += size(root->par->l) + 1; 
		root = root->par;
	}

	pnode L, R;
	split(root, L, R, pos - 1);
	return R;
}

pnode remove_right(pnode u)
{
	int pos = size(u->l);
	pnode root = u;

	while(root->par)
	{
		if(root->par->r == root) pos += size(root->par->l) + 1; 
		root = root->par;
	}

	pnode L, R, prv_pp = root->pp;
	root->pp = nullptr;
	split(root, L, R, pos);

	if(R) R->pp = u;
	L->pp = prv_pp;

	return L;
}

pnode merge_trees(pnode l, pnode r)
{
	pnode rt;
	if(r) r->pp = nullptr;
	merge(rt, l, r);
	return rt;
}

struct link_cut_tree
{
	pnode tr[MAXN];
	void new_node(int i, int col) { tr[i] = new node(col); }

	pnode access(pnode u)
	{
		u = remove_right(u);
		while(u->pp)
		{
			pnode p = remove_right(u->pp);
			u = merge_trees(p, u);
		}

		return u;
	}

	int query(pnode u)
	{
		u = access(u);
		return sum(u);
	}

	void cut(pnode u)
	{
		access(u);
		remove_left(u);
	}

	void link(pnode w, pnode u)
	{
		w = access(w);
		u = access(u);
		merge_trees(u, w);
	}
};

link_cut_tree lct;
int n, L;
int x[MAXN];
set<pair<int, int> > st;

const int OFFSET = 400042;

int fix(int x) { return x >= OFFSET ? x - OFFSET : x; }

void update_link(set<pair<int, int> >::iterator it)
{
	pnode p, u = lct.tr[fix(it->second)];
	lct.cut(u);

	if(fix(it->second) != 2 * n && (fix(it->second) & 1) == 0) p = lct.tr[fix(it->second) + 1];
	else p = lct.tr[fix(next(it)->second)];

	lct.link(u, p);
}

void init(int N, int L, int X[])
{
	n = N;
	::L = L;	

	lct.new_node(2 * N, 0);
	lct.new_node(2 * N + 1, 0);

	st.insert({-42, 2 * N});
	st.insert({inf, 2 * N + 1});
	for(int i = 0; i < N; i++)
	{
		lct.new_node(2 * i, 1);
		lct.new_node(2 * i + 1, 0);
		lct.link(lct.tr[2 * i], lct.tr[2 * i + 1]);

		st.insert({X[i], 2 * i});
		st.insert({X[i] + L, 2 * i + 1 + OFFSET});
		
		x[i] = X[i];
	}

	for(auto it = st.begin(); it != prev(st.end()); ++it)
		update_link(it);
}

void cut(int i) { lct.cut(lct.tr[fix(i)]); }

int update(int i, int y)
{
	auto it1 = st.lower_bound({x[i], 2 * i});
	auto it2 = st.lower_bound({x[i] + L, 2 * i + 1 + OFFSET});

	cut(it1->second);
	cut(it2->second);
	
	auto f = prev(it1), s = prev(it2);
		
	cut(prev(it1)->second);
	cut(prev(it2)->second);

	st.erase(it1);
	st.erase(it2);
	
	x[i] = y;

	it1 = st.insert({x[i], 2 * i}).first;
	it2 = st.insert({x[i] + L, 2 * i + 1 + OFFSET}).first;
	
	update_link(f);
	update_link(s);

	update_link(it1);
	update_link(it2);

	update_link(prev(it1));
	update_link(prev(it2));

	return lct.query(lct.tr[2 * n]);
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3