Cod sursa(job #2337818)

Utilizator LucaSeriSeritan Luca LucaSeri Data 6 februarie 2019 18:48:35
Problema Secv8 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <bits/stdc++.h>

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Node {
	Node *l = 0, *r = 0;
	int val, y;
	int c;
	bool rev;

	Node(int val): val(val), y(rng()), c(1), rev(false) {}

	void recalc();
};

int cnt(Node* t) {
	if(t) return t->c;
	return 0;
}

void Node::recalc() {
	c = cnt(l) + cnt(r) + 1;
	if(rev) {
		swap(l, r);
		if(l) l->rev ^= 1;
		if(r) r->rev ^= 1;
		rev = false;
	}
}

pair< Node*, Node* > split(Node *t, int k) {
	if(!t) return {};

	t->recalc();
	if(cnt(t->l) >= k) {
		auto pa = split(t->l, k);
		t->l = pa.second;
		t->recalc();
		return {pa.first, t};
	} else {
		auto pa = split(t->r, k - cnt(t->l) - 1);
		t->r = pa.first;
		t->recalc();
		return {t, pa.second};
	}
}

Node* join(Node *l, Node *r) {
	if(!l) return r;
	if(!r) return l;
	l->recalc();
	r->recalc();
	if(l->y > r->y) {
		l->r = join(l->r, r);
		l->recalc();
		return l;
	} else {
		r->l = join(l, r->l);
		r->recalc();
		return r;
	}
}

Node* ins(Node *t, Node *n, int k) {
	auto pa = split(t, k - 1);
	return join(join(pa.first, n), pa.second);
}

int access(Node *t, int k) {
	if(!t) assert(0);
	t->recalc();
	if(cnt(t->l) + 1 == k) return t->val;
	if(cnt(t->l) >= k) return access(t->l, k);
	return access(t->r, k - cnt(t->l) - 1);
}

void afis(Node *t, ostream & os) {
	if(!t) return;
	t->recalc();
	afis(t->l, os);
	os << t->val << ' ';
	afis(t->r, os);
}

Node* rev(Node *t, int a, int b) {
	auto pa = split(t, a - 1);
	auto u = split(pa.second, b-a+1);

	if(!u.first) assert(0);
	u.first->rev ^= 1;

	return join(join(pa.first, u.first), u.second);
}

Node* del(Node *t, int a, int b) {
	auto pa = split(t, a - 1);
	auto u = split(pa.second, b - a + 1);
	if(!u.first) assert(0);
	delete(u.first);
	u.first = 0;

	return join(pa.first, u.second);
}


int main() {
	ifstream f("secv8.in");
	ofstream g("secv8.out");

	Node *root = 0;
	int t, plm;
	f >> t >> plm;

	int a, b;
	while(t--) {
		char c;
		f >> c;
		f >> a;
		if(c != 'A') f >> b;
		if(c == 'I') {
			root = ins(root, new Node(b), a);
		}
		if(c == 'A') {
			g << access(root, a) << '\n';
		}
		if(c == 'R') {
			root = rev(root, a, b);
		}
		if(c == 'D') {			
			root = del(root, a, b);
		}
	}

	afis(root, g);
}