oj.uz

Submission #120821

# Submission time Handle Problem Language Result Execution time Memory
120821 2019-06-25T14:40:21 Z JustInCase Dancing Elephants (IOI11_elephants) C++17
100 / 100
 2112 ms 43612 KB 
#include <bits/stdc++.h>
#ifndef LOCAL
	#include "elephants.h"
#endif

const int32_t MAX_N = 150000;
const int32_t INF = 2e9;
const int32_t OFFSET = 1e6;
std::mt19937 mt(69);

struct Node {
	bool rev;
	int32_t sz, val, sum, prior;
	Node *l, *r, *par, *pp;	
	
	Node() {}
	Node(int32_t _val) : val(_val), sum(_val) {
		rev = false;

		sz = 1;
		prior = mt();

		l = nullptr;
		r = nullptr;
		par = nullptr;
		pp = nullptr;
	}

	static int32_t get_size(Node *x) {
		return (x ? x->sz : 0);
	}

	static int32_t get_sum(Node *x) {
		return (x ? x->sum : 0);
	}
	
	static void push_lazy(Node *x) {
		if(!x) {
			return;
		}

		if(x->rev) {
			std::swap(x->l, x->r);
			if(x->l) {
				x->l->rev ^= 1;
			}
			if(x->r) {
				x->r->rev ^= 1;
			}

			x->rev = false;
		}
	}

	static void recalc(Node *x) {
		if(!x) {
			return;
		}
		
		push_lazy(x);

		x->sz = get_size(x->l) + get_size(x->r) + 1;
		x->sum = get_sum(x->l) + get_sum(x->r) + x->val;

		x->par = nullptr;
		if(x->l) {
			x->l->par = x;
			if(x->l->pp) {
				x->pp = x->l->pp;
				x->l->pp = nullptr;
			}
		}
		if(x->r) {
			x->r->par = x;
			if(x->r->pp) {
				x->pp = x->r->pp;
				x->r->pp = nullptr;
			}
		}
	}

	static Node* merge(Node *x, Node *y) {
		push_lazy(x);
		push_lazy(y);

		if(!x) {
			return y;
		}
		if(!y) {
			return x;
		}

		if(x->prior > y->prior) {
			x->r = merge(x->r, y);
			recalc(x);
			return x;
		}
		else {
			y->l = merge(x, y->l);
			recalc(y);
			return y;
		}
	}

	static std::pair< Node*, Node* > split(Node *x, int32_t key, int32_t add = 0) {
		push_lazy(x);
		
		if(!x) {
			return { nullptr, nullptr };
		}

		int32_t currKey = add + get_size(x->l);
		if(currKey <= key) {
			auto aux = split(x->r, key, currKey + 1);
			x->r = aux.first;

			recalc(x);

			return { x, aux.second };
		}
		else {
			auto aux = split(x->l, key, add);
			x->l = aux.second;

			recalc(x);

			return { aux.first, x };
		}
	}

	static int32_t get_pos(Node *x) {
		int32_t pos = get_size(x->l);
		while(x->par) {
			if(x->rev) {
				pos = get_size(x) - pos - 1;
			}
			if(x->par->r == x) {
				pos += get_size(x->par->l) + 1;
			}
			x = x->par;
		}

		if(x->rev) {
			pos = get_size(x) - pos - 1;
		}
		return pos;
	}

	static Node* get_root(Node *x) {
		while(x->par) {
			x = x->par;
		}

		return x;
	}

	static Node* split_after(Node *x) {
		int32_t pos = get_pos(x);
		Node *root = get_root(x);

		Node *pp = root->pp;
		root->pp = nullptr;

		auto aux = split(root, pos);
		if(aux.second) {
			aux.second->pp = x;
		}
		root = aux.first;
		root->pp = pp;

		return root;
	}

	static Node* access(Node *x) {
		x = split_after(x);
		while(x->pp) {
			Node *u = x->pp;
			u = split_after(u);
			x->pp = nullptr;	
			x = merge(u, x);
		}
		return x;
	}

	static void reroot(Node *x) {
		x = access(x);
		x->rev ^= 1;
	}

	static void link(Node *x, Node *y) {
		reroot(x);
		x->pp = y;
	}

	static void cut(Node *x) {
		Node *u = access(x);
		split(u, get_size(u) - 2);
	}
};

int32_t n, l, x[MAX_N + 5];
std::set< std::pair< int32_t, int32_t > > s;
Node *nodes[2 * MAX_N + 5];

int32_t answer_query() {
	Node *u = Node::access(nodes[2 * n]);
	return Node::get_sum(u);
}

int32_t get_right_ind(int32_t p) {
	return (p > OFFSET ? p - OFFSET : p);
}

void fix_link(std::set< std::pair< int32_t, int32_t > >::iterator it) {
	Node *u, *v = nodes[get_right_ind(it->second)];
	Node::cut(v);

	if(get_right_ind(it->second) != 2 * n && get_right_ind(it->second) % 2 == 0) {
		u = nodes[get_right_ind(it->second) + 1];
	}
	else {
		u = nodes[get_right_ind(next(it)->second)];
	}

	Node::link(v, u);
}

void init(int32_t _n, int32_t _l, int32_t *_x) {
	n = _n;
	l = _l;
	
	for(int32_t i = 0; i < n; i++) {
		x[i] = _x[i];
		s.insert({ x[i], 2 * i });
		s.insert({ x[i] + l, 2 * i + 1 + OFFSET });
	
		nodes[2 * i] = new Node(1);
		nodes[2 * i + 1] = new Node(0);
	}

	s.insert({ -1, 2 * n });
	s.insert({ INF, 2 * n + 1 + OFFSET });

	nodes[2 * n] = new Node(0);
	nodes[2 * n + 1] = new Node(0);

	for(int32_t i = 0; i < n; i++) {
		Node::link(nodes[2 * i], nodes[2 * i + 1]);
	}
	
	for(auto it = s.begin(); it != prev(s.end()); it++) {
		fix_link(it);
	}
}

int32_t update(int32_t i, int32_t y) {
	auto it1 = s.lower_bound({ x[i], 2 * i });
	auto it2 = s.lower_bound({ x[i] + l, 2 * i + 1 + OFFSET });

	Node::cut(nodes[get_right_ind(it1->second)]);
	Node::cut(nodes[get_right_ind(it2->second)]);
	
	auto aux1 = prev(it1), aux2 = prev(it2);
	Node::cut(nodes[get_right_ind(prev(it1)->second)]);
	Node::cut(nodes[get_right_ind(prev(it2)->second)]);

	s.erase(it1);
	s.erase(it2);

	x[i] = y;

	it1 = s.insert({ y, 2 * i }).first;
	it2 = s.insert({ y + l, 2 * i + 1 + OFFSET }).first;

	fix_link(aux1);
	fix_link(aux2);

	fix_link(it1);
	fix_link(it2);

	fix_link(prev(it1));
	fix_link(prev(it2));

	return answer_query();
}

#ifdef LOCAL
	#include "grader.cpp"
#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 185 ms 4916 KB Output is correct
8 Correct 194 ms 6132 KB Output is correct
9 Correct 394 ms 14712 KB Output is correct
10 Correct 215 ms 14456 KB Output is correct
11 Correct 262 ms 14388 KB Output is correct
12 Correct 547 ms 14712 KB Output is correct
13 Correct 273 ms 14204 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 185 ms 4916 KB Output is correct
8 Correct 194 ms 6132 KB Output is correct
9 Correct 394 ms 14712 KB Output is correct
10 Correct 215 ms 14456 KB Output is correct
11 Correct 262 ms 14388 KB Output is correct
12 Correct 547 ms 14712 KB Output is correct
13 Correct 273 ms 14204 KB Output is correct
14 Correct 378 ms 7112 KB Output is correct
15 Correct 348 ms 8348 KB Output is correct
16 Correct 783 ms 15180 KB Output is correct
17 Correct 833 ms 20276 KB Output is correct
18 Correct 913 ms 20216 KB Output is correct
19 Correct 382 ms 20400 KB Output is correct
20 Correct 827 ms 20248 KB Output is correct
21 Correct 834 ms 20224 KB Output is correct
22 Correct 417 ms 19832 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 185 ms 4916 KB Output is correct
8 Correct 194 ms 6132 KB Output is correct
9 Correct 394 ms 14712 KB Output is correct
10 Correct 215 ms 14456 KB Output is correct
11 Correct 262 ms 14388 KB Output is correct
12 Correct 547 ms 14712 KB Output is correct
13 Correct 273 ms 14204 KB Output is correct
14 Correct 378 ms 7112 KB Output is correct
15 Correct 348 ms 8348 KB Output is correct
16 Correct 783 ms 15180 KB Output is correct
17 Correct 833 ms 20276 KB Output is correct
18 Correct 913 ms 20216 KB Output is correct
19 Correct 382 ms 20400 KB Output is correct
20 Correct 827 ms 20248 KB Output is correct
21 Correct 834 ms 20224 KB Output is correct
22 Correct 417 ms 19832 KB Output is correct
23 Correct 1566 ms 43612 KB Output is correct
24 Correct 1484 ms 43596 KB Output is correct
25 Correct 1352 ms 43600 KB Output is correct
26 Correct 828 ms 43600 KB Output is correct
27 Correct 630 ms 43440 KB Output is correct
28 Correct 1024 ms 6156 KB Output is correct
29 Correct 1000 ms 6132 KB Output is correct
30 Correct 1008 ms 6136 KB Output is correct
31 Correct 1010 ms 6132 KB Output is correct
32 Correct 976 ms 43032 KB Output is correct
33 Correct 709 ms 42368 KB Output is correct
34 Correct 692 ms 43236 KB Output is correct
35 Correct 628 ms 43520 KB Output is correct
36 Correct 1279 ms 42996 KB Output is correct
37 Correct 1777 ms 43416 KB Output is correct
38 Correct 957 ms 42232 KB Output is correct
39 Correct 845 ms 43272 KB Output is correct
40 Correct 954 ms 42268 KB Output is correct
41 Correct 2045 ms 43028 KB Output is correct
42 Correct 2112 ms 43248 KB Output is correct