Cod sursa(job #2596301)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 9 aprilie 2020 15:59:08
Problema Secv8 Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.49 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("secv8.in");
ofstream fout("secv8.out");

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

struct Treap
{
	int siz;
	int priority;
	int val;
	int lazy;
	
	Treap* left;
	Treap* right;
};

Treap* nill = new Treap{0, 0, 0, 0, nill, nill};
Treap* root = nill;

int siz(Treap* root)
{
	return root -> siz;
}

void update(Treap* root)
{
	if(root == nill)
		root -> siz = 0;
	else
		root -> siz = siz(root -> left) + siz(root -> right) + 1;
}

void propaga(Treap* root)
{
	if(root != nill && root -> lazy == 1)
	{
		root -> lazy = 0;
		root -> left -> lazy = 1 - root -> left -> lazy;
		root -> right -> lazy = 1 - root -> right -> lazy;
		swap(root -> left, root -> right);
	}
}

Treap* meld(Treap* st, Treap *dr)
{
	propaga(st);
	propaga(dr);
	
	update(st);
	update(dr);
	
	if(st == nill)
		return dr;
	
	if(dr == nill)
		return st;
	
	if(st -> priority < dr -> priority)
	{
		st -> right = meld(st -> right, dr);
		propaga(st);
		update(st);
		return st;
	}
	else
	{
		dr -> left = meld(st, dr -> left);
		propaga(dr);
		update(dr);
		return dr;
	}
}

pair <Treap*, Treap*> split(Treap* root, int key)
{
	pair <Treap*, Treap*> ans = {nill, nill};
	
	if(root == nill)
		return ans;
	
	propaga(root);
	update(root);
	
	int pos = siz(root -> left) + 1;
	
	if(pos == key)
	{
		ans.first = root -> left;
		root -> left = nill;
		ans.second = root;
		
		propaga(ans.second);
		update(ans.second);
		return ans;
	}
	
	if(pos < key)
	{
		pair <Treap*, Treap*> aux = split(root -> right, key - pos);
		ans.second = aux.second;
		root -> right = aux.first;
		ans.first = root;
	}
	
	if(pos > key)
	{
		pair <Treap*, Treap*> aux = split(root -> left, key);
		ans.first = aux.first;
		root -> left = aux.second;
		ans.second = root;
	}
	
	propaga(ans.first);
	propaga(ans.second);
	
	update(ans.first);
	update(ans.second);
	
	return ans;
}

void print(Treap* root)
{
	if(root == nill)
		return ;
	
	propaga(root);
	
	print(root -> left);
	fout << root -> val << ' ';
	print(root -> right);
}

Treap* insert(Treap* root, int pos, int val)
{
	pair <Treap*, Treap*> aux = split(root, pos);
	Treap* solo = new Treap{1, uniform_int_distribution<int>(1, 2000000000)(rng), val, 0, nill, nill};
	return meld(meld(aux.first, solo), aux.second);
}

Treap* reverse(Treap* root, int x, int y)
{
	pair <Treap*, Treap*> aux1 = split(root, x);
	pair <Treap*, Treap*> aux2 = split(aux1.second, y + 1);
	
	aux2.first -> lazy = 1 - aux2.first -> lazy;
	
	return meld(meld(aux1.first, aux2.first), aux2.second);
}

Treap* del(Treap* root, int x, int y)
{
	pair <Treap*, Treap*> aux1 = split(root, y + 1);
	pair <Treap*, Treap*> aux2 = split(aux1.first, x);
	
	return meld(aux2.first, aux1.second);
}

int search(Treap* root, int key)
{
	if(root == nill)
		return 0;
		
	propaga(root);
	update(root);
	
	int pos = siz(root -> left) + 1;
	
	if(key == pos)
		return root -> val;
	
	if(key < pos)
		return search(root -> left, key);
	else
		return search(root -> right, key - pos);
}

main()
{
	int n, p;
	fin >> n >> p;
	
	for(int i = 1; i <= n; ++i)
	{
		char op;
		fin >> op;
		
		if(op == 'I')
		{
			int pos, val;
			fin >> pos >> val;
			
			root = insert(root, pos, val);
			continue;
		}
		
		if(op == 'A')
		{
			int pos;
			fin >> pos;
			
			fout << search(root, pos) << '\n';
			continue;
		}
		
		if(op == 'R')
		{
			int x, y;
			fin >> x >> y;
			
			root = reverse(root, x, y);
			continue;
		}
		
		if(op == 'D')
		{
			int x, y;
			fin >> x >> y;
			
			root = del(root, x, y);
			continue;
		}
	}
	
	print(root);
}