제출 #120821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120821		JustInCase	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	100 / 100	2112 ms	43612 KiB

elephants

#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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3