gistfile1.cpp

#include <stdio.h>


class Tree {

protected:

class Node {
	private:
		int _value;
		Node *_left;
		Node *_right;

	public:
		Node(int value) {
			_value = value;
			_left = NULL;
			_right = NULL;
		} Node():_value(0), _left(NULL), _right(NULL) {
		}

		void left(Node * ptr) {
			_left = ptr;
		}

		void right(Node * ptr) {
			_right = ptr;
		}

		void value(int iValue) {
			_value = iValue;
		}

		int value() {
			return _value;
		}

		Node *left(void) {
			return _left;
		}

		Node *right(void) {
			return _right;
		}
	};

Node * head;

public:

	Tree():head(NULL) {	} 

	Tree(int value) {
		head= new Node(value);
	}

	bool Add(Node * node, int value) {
		if (head == NULL) {
			Node *node = new Node(value);
			head = node;
			return true;
		}
		if (value >= node->value()) {
			if (node->right() != NULL)
				return Add(node->right(), value);
			else {
				Node *newNode = new Node(value);
				node->right(newNode);
				return true;
			}
		} else {
			if (node->left() != NULL)
				Add(node->left(), value);
			else {
				Node *newNode = new Node(value);
				node->left(newNode);
				return true;
			}
		}
		return false;
	}

	bool Add(int value) {
		if (head == NULL) {
			Node *node = new Node(value);
			head = node;
			return true;
		}
		if (value >= head->value()) {
			if (head->right() != NULL)
				return Add(head->right(), value);
			else {
				Node *newNode = new Node(value);
				head->right(newNode);
				return true;
			}
		} else {
			if (head->left() != NULL)
				return Add(head->left(), value);
			else {
				Node *newNode = new Node(value);
				head->left(newNode);
				return true;
			}
		}
	}

	Node *RemoveNode(Node * root, int x)
	{

		Node *t = new Node;
		if (x == root->value()) {
			if (root->left() == NULL) {
				t = root->right();
				delete root;
				return t;
			}
			t = root->left();
			while (t->right()) {
				t = t->right();
			}
			t->right(root->right());
			return root->left();
		}
		if (x < root->value())
			root->left(RemoveNode(root->left(), x));
		else
			root->right(RemoveNode(root->right(), x));
		return root;
	}

	bool search(int value, Node *node) {
		while (node != NULL){
			if (value == node->value()) {
				return true;
			} 
			else {
				if(value <= node->value()) return search(value, node->left());
				else return search(value, node->right());
			}
		}
		return false;
	}

	bool search(int value) {
		while (head != NULL){
			if (value == head->value()) {
				return true;
			} 
			else {
				if(value <= head->value()) return search(value, head->left());
				else return search(value, head->right());
			}
		}
		return false;
	}

	int get_height(){
		struct stack{
			Node* node;
			stack* stckNext,*stckPrev;
		}*stck;
		stck = new stack;
		stck->node = head;
		stck->stckNext = NULL;
		stck->stckPrev = NULL;

		int maxheight = 1;
		for(int i = 1; i <=2 ; i++)
		{
			int temp_height=1;
			Node* temp = head;
			while(temp->left()!=NULL){
				stck->stckNext = new stack;
				stck->stckNext->stckPrev = stck;
				stck->stckNext->node = temp->left();
				temp_height++;
				temp = temp->left();
				stck = stck->stckNext;
			}
			Node* check = NULL;
			while(stck->stckPrev!=NULL){
				if(stck->node->left()!=NULL && check!=stck->node->left() && check!=stck->node->right()){
					stck->stckNext = new stack;
					stck->stckNext->stckPrev = stck;
					stck->stckNext->node = stck->node->left();
					stck = stck->stckNext;
					temp_height++;
				}
				else {
					if(stck->node->right()!=NULL && check!=stck->node->right()){
							temp_height++;
							check = stck->node;
							stck->stckNext = new stack;
							stck->stckNext->node = stck->node->right();
							stck->stckNext->stckPrev = stck;
							stck = stck->stckNext;
							continue;
					}
					if(temp_height > maxheight)
						maxheight = temp_height;
					temp_height--;
					check = stck->node;
					stck=stck->stckPrev;
					delete stck->stckNext;
				}
			}
			check = head->left(); //buffer
			head->left(head->right());
			head->right(check);
		}
		return maxheight;
	}

};

//********************************************************
//Декартово дерево:
//********************************************************
class Treap : public Tree{
class TreapNode: public Tree::Node {
    int _priority;
public:
	void priority(int value) { _priority = value; }
	int priority(void) { return _priority; }
    TreapNode(int key, int priority) : Tree::Node(key), _priority(priority) {}
};
public:

Treap(int key, int priority){
	Treap::head = new TreapNode(key,priority);
}

TreapNode* Merge(TreapNode* left, TreapNode* right)
{
        if( left == 0 || right == 0 ) {
                return left == 0 ? right : left;
        }
        if( left->priority() > right->priority() ) {
                left->right(Merge((TreapNode*)left->right(), right));
                return left;
    }
        right->left(Merge(left, (TreapNode*)right->left()));
        return right;
}

void Split(TreapNode* currentNode, int key, TreapNode*& left, TreapNode*& right)
{
        if( currentNode == 0 ) {
                left = 0;
                right = 0;
        } else if( currentNode->value() <= key ) {
                // Сокращенный вариант - Split(currentNode->Right, key, currentNode->Right, right);
                TreapNode* tempLeft = 0;
                TreapNode* tempRight = 0;
                Split((TreapNode*)currentNode->right(), key, tempLeft, tempRight);
                right = tempRight;
                left = currentNode;
                left->right(tempLeft);
    } else {
                // Сокращенный вариант - Split(currentNode->Left, key, left, currentNode->Left);
				TreapNode* tempLeft = 0;
                TreapNode* tempRight = 0;
                Split((TreapNode*)currentNode->left(), key, tempLeft, tempRight);//a, t->l);
                left = tempLeft;
                right = currentNode;
                right->left(tempRight);
    }
}

void Add(int key, int priority) {
        TreapNode* node = new TreapNode(key, priority);
        TreapNode* splitLeft = 0;
        TreapNode* splitRight = 0;
        Split((TreapNode*)head, key, splitLeft, splitRight);
		Treap::head = Merge(Merge(splitLeft, node), splitRight);
}

void RemoveNode(int key)
{
        TreapNode* splitLeft = 0;
        TreapNode* splitRight = 0;
        Split((TreapNode*)head, key - 1, splitLeft, splitRight);
        TreapNode* splitRightLeft = 0;
		TreapNode* splitRightRight = 0;
		Split(splitRight, key, splitRightLeft, splitRightRight);
		delete splitRightLeft;
        head = Merge(splitLeft, splitRightRight);
}

};

void Get_Tree_and_Treap_From_Keyboard(size_t size, Treap **_treap, Tree **_tree){
		int temp_value, temp_priority;
		scanf("%d",&temp_value);
		scanf("%d",&temp_priority);
		*_treap = new Treap(temp_value, temp_priority);
		*_tree= new Tree(temp_value);
		--size;
		while(size>0){
			scanf("%d",&temp_value);
			scanf("%d",&temp_priority);
			(*_treap)->Add(temp_value, temp_priority);
			(*_tree)->Add(temp_value);
			--size;
		}
	}

int main(int argc, char argv[]){

	size_t size;
	scanf("%d ",&size);
	Tree* myTree;
	Treap* myTreap;
	Get_Tree_and_Treap_From_Keyboard(size, &myTreap, &myTree);
	printf("%d",myTree->get_height() - myTreap->get_height());
	return 0;
}