Cod sursa(job #449563)

Utilizator katakunaCazacu Alexandru katakuna Data 6 mai 2010 16:44:02
Problema Secv8 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.22 kb
#include <cstdio>
#include <stdlib.h>
#include <ctime>

#define Pmax (1 << 25)

struct treap {
	int key, priority, nr, rev;
	treap *left, *right;
	
	treap (int priority, int key, int nr, int rev, treap* left, treap* right) {
		this->key = key;
		this->priority = priority;
		this->nr = nr;
		this->rev = rev;
		this->left = left;
		this->right = right;
	}
} *R, *nil, *A, *B, *C, *R2;

void rot_left (treap* &nod) {
	
	treap *fiu = nod->left;
	nod->left = fiu->right; fiu->right = nod;
	
	nod->nr = nod->left->nr + nod->right->nr + 1;
	nod = fiu;
	nod->nr = nod->left->nr + nod->right->nr + 1;
}

void rot_right (treap* &nod) {
	
	treap *fiu = nod->right;
	nod->right = fiu->left; fiu->left = nod;
	
	nod->nr = nod->left->nr + nod->right->nr + 1;
	nod = fiu;
	nod->nr = nod->left->nr + nod->right->nr + 1;
}

void balance (treap* &nod) {
	
	if (nod->left->priority > nod->priority) rot_left (nod);
	if (nod->right->priority > nod->priority) rot_right (nod);
	
	nod->nr = nod->left->nr + nod->right->nr + 1;
}

void nod_rev (treap* &nod) {
	
	if (nod->rev == 0) return;
	
	treap *l = nod->left, *r = nod->right;
	nod->left = r; nod->right = l;
	
	if (nod->left != nil) nod->left->rev^= 1;
	if (nod->right != nil) nod->right->rev^= 1;
	
	nod->rev = 0;
}

void insert (treap* &nod, int priority, int key, int poz) {
	
	if (nod != nil) {
		nod_rev (nod);
		if (nod->left != nil) nod_rev (nod->left);
		if (nod->right != nil) nod_rev (nod->right);
	}
	
	if (nod == nil) {
		nod = new treap (priority, key, 1, 0, nil, nil);
		return ;
	}
	
	if (poz <= nod->left->nr + 1)
		insert (nod->left, priority, key, poz);
	else
		insert (nod->right, priority, key, poz - (nod->left->nr + 1));
	
	balance (nod);
}

int acces (treap *nod, int poz) {
	
	if (nod != nil) {
		nod_rev (nod);
		if (nod->left != nil) nod_rev (nod->left);
		if (nod->right != nil) nod_rev (nod->right);
	}
	
	if (poz == nod->left->nr + 1) 
		return nod->key;
	
	if (poz <= nod->left->nr)
		return acces (nod->left, poz);
	else
		return acces (nod->right, poz - nod->left->nr - 1);
}

void erase (treap* &nod, int nr) {
	
	if (nod != nil) {
		nod_rev (nod);
		if (nod->left != nil) nod_rev (nod->left);
		if (nod->right != nil) nod_rev (nod->right);
	}
	
	if (nr <= nod->left->nr)
		erase (nod->left, nr);
	else{
		if (nr > nod->left->nr + 1)
			erase (nod->right, nr - nod->left->nr - 1);
		else {
			
			if (nod->left == nil && nod->right == nil) {
				delete nod, nod = nil;
				return ;
			}
			
			if (nod->left->priority > nod->right->priority)
				rot_left (nod);
			else
				rot_right (nod);
			
			erase (nod, nr);
		}
	}
	
	nod->nr = nod->left->nr + nod->right->nr + 1;
}

void parcurge (treap *nod) {
	
	if (nod == nil) 
		return ;
	
	if (nod != nil) {
		nod_rev (nod);
		if (nod->left != nil) nod_rev (nod->left);
		if (nod->right != nil) nod_rev (nod->right);
	}
	
	parcurge (nod->left);
	printf ("%d ", nod->key);
	parcurge (nod->right);
}

void del (int a, int b) {
	
	insert (R, Pmax + 1, 0, a);
	A = R->left; B = R->right;
	delete R, R = B; 
	
	insert (R, Pmax + 1, 0, b + 1 - a + 1);
	B = R->right;
	delete R, R = nil;
	
	R = new treap (0, 0, A->nr + B->nr + 1, 0, A, B);
	erase (R, R->left->nr + 1);
}

void reverse (int a, int b) {
	
	treap *A, *B, *C, *R2;
	
	insert (R, Pmax + 1, 0, a);
	A = R->left; B = R->right;
	
	insert (B, Pmax + 1, 0, b + 1 - a + 1);
	C = B->right; B = B->left;
	
	if (B != nil) 
		B->rev^= 1;
	
	
	R2 = new treap (0, 0, A->nr + B->nr + 1, 0, A, B);
	erase (R2, R2->left->nr + 1);
	
	R = new treap (0, 0, R2->nr + C->nr + 1, 0, R2, C);
	erase (R, R->left->nr + 1);
	
}

int main () {

	freopen ("secv8.in", "r", stdin);
	freopen ("secv8.out", "w", stdout);

	int i, T, x, y; 
	char tip;
	
	srand (time (0));
	R = nil = new treap (0, 0, 0, 0, NULL, NULL);
	for (scanf ("%d %d\n", &T, &i); T; T--) {
		scanf ("%c ", &tip);
		if (tip == 'A') {
			scanf ("%d\n", &x);
			printf ("%d\n", acces (R, x));
		}
		else {
			scanf ("%d %d\n", &x, &y);
			if (tip == 'I') insert (R, rand () % Pmax + 1, y, x);
			if (tip == 'R') reverse (x, y);
			if (tip == 'D') del (x, y);
		}
	}
	
	parcurge (R);
	
	return 0;
}