oj.uz

Submission #55017

# Submission time Handle Problem Language Result Execution time Memory
55017 2018-07-05T20:12:06 Z radoslav11 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 2766 ms 149456 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;

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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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