답안 #55017 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55017	2018-07-05T20:12:06 Z	radoslav11	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	2766 ms	149456 KB

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

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

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	456 KB	Output is correct
5	Correct	3 ms	548 KB	Output is correct
6	Correct	3 ms	548 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	456 KB	Output is correct
5	Correct	3 ms	548 KB	Output is correct
6	Correct	3 ms	548 KB	Output is correct
7	Correct	413 ms	5340 KB	Output is correct
8	Correct	366 ms	7692 KB	Output is correct
9	Correct	703 ms	17052 KB	Output is correct
10	Correct	380 ms	18372 KB	Output is correct
11	Correct	569 ms	19688 KB	Output is correct
12	Correct	795 ms	21092 KB	Output is correct
13	Correct	491 ms	22392 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	456 KB	Output is correct
5	Correct	3 ms	548 KB	Output is correct
6	Correct	3 ms	548 KB	Output is correct
7	Correct	413 ms	5340 KB	Output is correct
8	Correct	366 ms	7692 KB	Output is correct
9	Correct	703 ms	17052 KB	Output is correct
10	Correct	380 ms	18372 KB	Output is correct
11	Correct	569 ms	19688 KB	Output is correct
12	Correct	795 ms	21092 KB	Output is correct
13	Correct	491 ms	22392 KB	Output is correct
14	Correct	658 ms	22392 KB	Output is correct
15	Correct	681 ms	22392 KB	Output is correct
16	Correct	1126 ms	27324 KB	Output is correct
17	Correct	1271 ms	34240 KB	Output is correct
18	Correct	1360 ms	36140 KB	Output is correct
19	Correct	686 ms	38516 KB	Output is correct
20	Correct	1208 ms	40280 KB	Output is correct
21	Correct	1188 ms	42352 KB	Output is correct
22	Correct	711 ms	43936 KB	Output is correct

Subtask #5
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	456 KB	Output is correct
5	Correct	3 ms	548 KB	Output is correct
6	Correct	3 ms	548 KB	Output is correct
7	Correct	413 ms	5340 KB	Output is correct
8	Correct	366 ms	7692 KB	Output is correct
9	Correct	703 ms	17052 KB	Output is correct
10	Correct	380 ms	18372 KB	Output is correct
11	Correct	569 ms	19688 KB	Output is correct
12	Correct	795 ms	21092 KB	Output is correct
13	Correct	491 ms	22392 KB	Output is correct
14	Correct	658 ms	22392 KB	Output is correct
15	Correct	681 ms	22392 KB	Output is correct
16	Correct	1126 ms	27324 KB	Output is correct
17	Correct	1271 ms	34240 KB	Output is correct
18	Correct	1360 ms	36140 KB	Output is correct
19	Correct	686 ms	38516 KB	Output is correct
20	Correct	1208 ms	40280 KB	Output is correct
21	Correct	1188 ms	42352 KB	Output is correct
22	Correct	711 ms	43936 KB	Output is correct
23	Correct	2273 ms	69452 KB	Output is correct
24	Correct	2069 ms	74396 KB	Output is correct
25	Correct	2113 ms	79440 KB	Output is correct
26	Correct	1572 ms	84444 KB	Output is correct
27	Correct	1182 ms	89236 KB	Output is correct
28	Correct	1746 ms	89236 KB	Output is correct
29	Correct	1916 ms	89236 KB	Output is correct
30	Correct	1739 ms	89236 KB	Output is correct
31	Correct	1712 ms	89236 KB	Output is correct
32	Correct	1624 ms	105560 KB	Output is correct
33	Correct	1482 ms	109468 KB	Output is correct
34	Correct	1283 ms	114052 KB	Output is correct
35	Correct	908 ms	119132 KB	Output is correct
36	Correct	1637 ms	123372 KB	Output is correct
37	Correct	2645 ms	128312 KB	Output is correct
38	Correct	1605 ms	132064 KB	Output is correct
39	Correct	1681 ms	136768 KB	Output is correct
40	Correct	1588 ms	140388 KB	Output is correct
41	Correct	2594 ms	144932 KB	Output is correct
42	Correct	2766 ms	149456 KB	Output is correct

답안 #55017

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 47.0 / 47.0

Subtask #5 3.0 / 3.0

Subtask #1
10.0 / 10.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
47.0 / 47.0

Subtask #5
3.0 / 3.0