Cod sursa(job #2454467)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 8 septembrie 2019 16:30:52
Problema Secv8 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("secv8.in");
ofstream fo("secv8.out");

struct Treap {
	int pr;
	Treap *st, *dr;
	int val, siz;
	bool rev;  } *NIL;

int n, junk;
Treap *root;

static void link_start() {
	srand(time(NULL));
	NIL = new Treap; *NIL = {-1, NIL, NIL, 1, 0, 0};
	root = NIL; }

Treap *make_nod(int val = 0) {
	return new Treap {rand(), NIL, NIL, val, 1, false}; }

static void reset(Treap *nod) {
	nod->siz = nod == NIL ? 0 : 1 + nod->st->siz + nod->dr->siz; }

static void prop(Treap *nod) {
	if (nod->rev) {
		nod->rev^= true;
		nod->st->rev^= true;
		nod->dr->rev^= true;
		swap(nod->st, nod->dr); } }

static pair<Treap*, Treap*> split(Treap *nod, int k) {
	if (nod == NIL)
		return make_pair(NIL, NIL);
	prop(nod);
	if (nod->st->siz >= k) { /// ?
		auto tmp = split(nod->st, k);
		nod->st = tmp.second;
		reset(nod);
		return make_pair(tmp.first, nod); }
	else {
		auto tmp = split(nod->dr, k - nod->st->siz - 1);
		nod->dr = tmp.first;
		reset(nod);
		return make_pair(nod, tmp.second); } }

static Treap *join(Treap *a, Treap *b) {
	if (a == NIL) return b;
	if (b == NIL) return a;
	prop(a), prop(b);
	if (a->pr >= b->pr) {
		a->dr = join(a->dr, b);
		reset(a);
		return a; }
	else {
		b->st = join(a, b->st);
		reset(b);
		return b; } }

static int kth(Treap *nod, int k) {
	if (nod == NIL) return -1;
	prop(nod);
	if (nod->st->siz + 1 == k)
		return nod->val;
	if (nod->st->siz >= k)
		return kth(nod->st, k);
	else
		return kth(nod->dr, k - nod->st->siz - 1); }

static Treap *baga(int pos, int val) {
	auto t = split(root, pos - 1);
	return join(t.first, join(make_nod(val), t.second)); }

static Treap *scoate(int l, int r) {
	auto a = split(root, r);
	auto b = split(a.first, l - 1);
	return join(b.first, a.second); }

static Treap *invarte(int l, int r) {
	auto a = split(root, r);
	auto b = split(a.first, l - 1);
	b.second->rev^= true;
	return join(b.first, join(b.second, a.second)); }

static void dfs(Treap *nod) {
	if (nod == NIL) return;
	prop(nod);
	if (nod->st)
		dfs(nod->st);
	fo << nod->val << ' ';
	if (nod->dr)
		dfs(nod->dr); }

int main() {
	link_start();
	fi >> n >> junk;

	while (n--) {
		char op;
		fi >> op;
		switch (op) {
		case 'I': { // insert
			int pos, val;
			fi >> pos >> val;
			root = baga(pos, val);
			break; }
		case 'A': { // access
			int pos;
			fi >> pos;
			fo << kth(root, pos) << '\n';
			break; }
		case 'R': { // reverse
			int l, r;
			fi >> l >> r;
			root = invarte(l, r);
			break; }
		case 'D': { // delete
			int l, r;
			fi >> l >> r;
			root = scoate(l, r);
			break; } } }

	dfs(root);
	fo << endl;

	return 0; }