oj.uz

답안 #55016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55016 2018-07-05T20:03:40 Z radoslav11 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
10 / 100
 3 ms 732 KB 
#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;

void update_link(set<pair<int, int> >::iterator it)
{

	pnode p, u = lct.tr[it->second];
	lct.cut(u);

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

	lct.link(u, p);
}

void init(int N, int L, int X[])
{
	n = N;
	L++;
	::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});
		
		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[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});

	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}).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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 3 ms 616 KB Output is correct

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Incorrect 2 ms 732 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Incorrect 2 ms 732 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Incorrect 2 ms 732 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Incorrect 2 ms 732 KB Output isn't correct
5 Halted 0 ms 0 KB -