Submission #198933

# Submission time Handle Problem Language Result Execution time Memory
198933 2020-01-28T08:33:37 Z QCFium Dancing Elephants (IOI11_elephants) C++14
0 / 100
6 ms 376 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_;
	a.resize(n);
	for (int i = 0; i < n; i++) a[i] = x[i];
	
	nodes_set.insert({-2000000001, 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({2000000001, 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 + 1, 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;
		}
	}
	
	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);
  ~~~~~^~~~~~~~~~
# 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 Incorrect 6 ms 376 KB Output isn't correct
# 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 Incorrect 6 ms 376 KB Output isn't correct
# 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 Incorrect 6 ms 376 KB Output isn't correct
# 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 Incorrect 6 ms 376 KB Output isn't correct
# 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 Incorrect 6 ms 376 KB Output isn't correct