oj.uz

Submission #198940

# Submission time Handle Problem Language Result Execution time Memory
198940 2020-01-28T08:38:43 Z QCFium Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5717 ms 36716 KB 
#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct LCT {
#define l ch[0]
#define r ch[1]
	struct Node {
		Node *p;
		Node *ch[2];
		int val;
		int sum;
		int size;
		void fetch() {
			size = 1 + l->size + r->size;
			sum = val + l->sum + r->sum;
		}
		void rotate(bool dir) {
			Node *new_root = ch[!dir], *parent = p;
			ch[!dir] = new_root->ch[dir];
			ch[!dir]->p = this;
			new_root->ch[dir] = this;
			p = new_root;
			fetch(), new_root->fetch();
			new_root->p = parent;
			if (parent->l == this) parent->l = new_root;
			else if (parent->r == this) parent->r = new_root;
		}
		bool is_root() {
			return p == LCT::NONE || (p->l != this && p->r != this);
		}
	};
	void splay(Node *node) {
		while (!node->is_root()) {
			Node *p = node->p;
			if (p->is_root()) {
				p->rotate(p->l == node);
			} else {
				Node *pp = p->p;
				bool flag1 = pp->l == p, flag2 = p->l == node;
				if (flag1 == flag2) pp->rotate(flag1);
				p->rotate(flag2);
				if (flag1 != flag2) pp->rotate(flag1);
			}
		}
	}
	Node *expose(Node *start) {
		Node *prev = NONE;
		for (Node *cur = start; cur != NONE; cur = cur->p) {
			splay(cur);
			cur->r = prev;
			cur->fetch();
			prev = cur;
		}
		splay(start);
		return prev;
	}
	void link(Node *child, Node *parent) {
		// std::cerr << "link " << (child - nodes - 1) << "->" << (parent - nodes - 1) << std::endl;
		assert(get_root(child) != get_root(parent));
		expose(child);
		expose(parent);
		child->p = parent;
		parent->r = child;
		parent->fetch();
	}
	void cut(Node *child) {
		// std::cerr << "cut " << (child - nodes - 1) << std::endl;
		expose(child);
		Node *parent = child->l;
		parent->p = NONE;
		child->l = NONE;
		child->fetch();
	}
	Node *get_root(Node *node) {
		expose(node);
		for (; node->l != NONE; node = node->l);
		return node;
	}
	static Node *nodes, *NONE;
	static int head;
	LCT () {
		if (!head) nodes[head++] = {NONE, {NONE, NONE}, 0, 0, 0};
	}
	Node *new_node(int val) {
		return &(nodes[head++] = {NONE, {NONE, NONE}, val, val, 1});
	}
#undef l
#undef r
};
LCT::Node *LCT::nodes = (Node *) malloc(sizeof(Node) * 1000000), *LCT::NONE = nodes;
int LCT::head = 0;

struct Comp {
	bool operator () (std::pair<int, int> a, std::pair<int, int> b) {
		if (a.first != b.first) return a.first < b.first;
		if ((a.second & 1) != (b.second & 1)) return (a.second & 1) < (b.second & 1);
		return a.second < b.second;
	}
};

int n, l;
std::vector<int> a;
LCT tree;
std::vector<LCT::Node *> nodes;
std::set<std::pair<int, int>, Comp> nodes_set;

template<class T>
void erase(T itr) {
	if ((std::prev(itr)->second & 1) == 0) {
		tree.cut(nodes[std::prev(itr)->second]);
		tree.link(nodes[std::prev(itr)->second], nodes[std::next(itr)->second]);
	}
}
template<class T>
void insert(T itr) {
	if ((std::prev(itr)->second & 1) == 0) {
		tree.cut(nodes[std::prev(itr)->second]);
		tree.link(nodes[std::prev(itr)->second], nodes[itr->second]);
	}
}

int update(int i, int pos) {
	// erase
	auto r0 = nodes_set.find({a[i], i * 2 + 1});
	auto r1 = nodes_set.find({a[i] + l, i * 2 + 2});
	assert(r0 != nodes_set.end());
	assert(r1 != nodes_set.end());
	
	erase(r0);
	nodes_set.erase(r0);
	erase(r1);
	nodes_set.erase(r1);
	a[i] = pos;
	r0 = nodes_set.insert({a[i], i * 2 + 1}).first;
	r1 = nodes_set.insert({a[i] + l, i * 2 + 2}).first;
	tree.cut(nodes[r1->second]);
	tree.link(nodes[r1->second], nodes[std::next(r1)->second]);
	insert(r0);
	insert(r1);
	
	tree.expose(nodes[0]);
	return nodes[0]->sum;
}

void init(int n_, int l_, int x[]) {
	n = n_;
	l = l_ + 1;
	a.resize(n);
	for (int i = 0; i < n; i++) a[i] = x[i];
	
	nodes_set.insert({-2000000002, nodes.size()});
	nodes.push_back(tree.new_node(0));
	for (int i = 0; i < n; i++) {
		auto r0 = nodes_set.insert({a[i], nodes.size()}).first;
		nodes.push_back(tree.new_node(1));
		insert(r0);
		auto r1 = nodes_set.insert({a[i] + l, nodes.size()}).first;
		nodes.push_back(tree.new_node(0));
		insert(r1);
		tree.link(nodes[r0->second], nodes[r1->second]);
	}
	auto tmp = nodes_set.insert({2000000002, nodes.size()}).first;
	nodes.push_back(tree.new_node(0));
	insert(tmp);
}

/*
int main() {
	int n = ri(), l = ri();
	int a[n];
	for (auto &i : a) i = ri();
	assert(std::is_sorted(a, a + n));
	
	init(n, l, a);
	
	int q = ri();
	for (int i = 0; i < q; i++) {
		int index = ri(), pos = ri();
		int r0 = update(index, pos);
		a[index] = pos;
		int b[n];
		memcpy(b, a, sizeof(a));
		std::sort(b, b + n);
		int r1 = 0;
		for (int i = 0; i < n; ) {
			int max = b[i] + l;
			for (; i < n && b[i] <= max; i++);
			r1++;
		}
		if (r0 != r1) {
			std::cerr << "FAILED correct:" << r1 << " wrong:" << r0 << std::endl;
		}
		std::cerr << r0 << std::endl;
	}
	
	return 0;
}
//*/

Compilation message

elephants.cpp: In function 'int ri()':
elephants.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 6 ms 508 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 4207 ms 4488 KB Output is correct
8 Correct 5717 ms 5492 KB Output is correct
9 Correct 215 ms 12396 KB Output is correct
10 Correct 130 ms 12012 KB Output is correct
11 Correct 140 ms 12204 KB Output is correct
12 Correct 416 ms 12268 KB Output is correct
13 Correct 149 ms 11884 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 6 ms 508 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 4207 ms 4488 KB Output is correct
8 Correct 5717 ms 5492 KB Output is correct
9 Correct 215 ms 12396 KB Output is correct
10 Correct 130 ms 12012 KB Output is correct
11 Correct 140 ms 12204 KB Output is correct
12 Correct 416 ms 12268 KB Output is correct
13 Correct 149 ms 11884 KB Output is correct
14 Correct 206 ms 6256 KB Output is correct
15 Correct 155 ms 7152 KB Output is correct
16 Correct 567 ms 12780 KB Output is correct
17 Correct 623 ms 17260 KB Output is correct
18 Correct 615 ms 17048 KB Output is correct
19 Correct 197 ms 17260 KB Output is correct
20 Correct 638 ms 17132 KB Output is correct
21 Correct 611 ms 17132 KB Output is correct
22 Correct 211 ms 16748 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 6 ms 508 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 4207 ms 4488 KB Output is correct
8 Correct 5717 ms 5492 KB Output is correct
9 Correct 215 ms 12396 KB Output is correct
10 Correct 130 ms 12012 KB Output is correct
11 Correct 140 ms 12204 KB Output is correct
12 Correct 416 ms 12268 KB Output is correct
13 Correct 149 ms 11884 KB Output is correct
14 Correct 206 ms 6256 KB Output is correct
15 Correct 155 ms 7152 KB Output is correct
16 Correct 567 ms 12780 KB Output is correct
17 Correct 623 ms 17260 KB Output is correct
18 Correct 615 ms 17048 KB Output is correct
19 Correct 197 ms 17260 KB Output is correct
20 Correct 638 ms 17132 KB Output is correct
21 Correct 611 ms 17132 KB Output is correct
22 Correct 211 ms 16748 KB Output is correct
23 Correct 1020 ms 36576 KB Output is correct
24 Correct 967 ms 36576 KB Output is correct
25 Correct 750 ms 36704 KB Output is correct
26 Correct 417 ms 36716 KB Output is correct
27 Correct 390 ms 36448 KB Output is correct
28 Correct 480 ms 6008 KB Output is correct
29 Correct 480 ms 6136 KB Output is correct
30 Correct 489 ms 6008 KB Output is correct
31 Correct 474 ms 6008 KB Output is correct
32 Correct 424 ms 36004 KB Output is correct
33 Correct 408 ms 35472 KB Output is correct
34 Correct 416 ms 36220 KB Output is correct
35 Correct 405 ms 36576 KB Output is correct
36 Correct 970 ms 36064 KB Output is correct
37 Correct 1265 ms 36448 KB Output is correct
38 Correct 467 ms 35168 KB Output is correct
39 Correct 470 ms 36192 KB Output is correct
40 Correct 457 ms 35424 KB Output is correct
41 Correct 1617 ms 36088 KB Output is correct
42 Correct 1623 ms 36320 KB Output is correct