Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <stdio.h>
- #include <cstdlib>
- using namespace std;
- struct Treap
- {
- long long key;
- long long priority;//rand();
- //long long value=0;
- //long long sum=0;
- Treap* left=nullptr;
- Treap* right=nullptr;
- };
- /*
- long long sum(Treap* t)
- {
- if(t==nullptr)
- return 0;
- return t->sum;
- }
- void update(Treap* t)
- {
- t->sum=t->value+sum(t->left)+sum(t->right);
- }
- */
- Treap* merge(Treap* left, Treap* right)
- {
- if(right==nullptr)
- {
- return left;
- }
- if(left==nullptr)
- {
- return right;
- }
- if(left->priority>right->priority)
- {
- left->right=merge(left->right, right);
- //update(left);
- return left;
- }
- right->left=merge(left, right->left);
- //update(right);
- return right;
- }
- void split(Treap* treap, long long key, Treap*& left, Treap*& right)
- {
- if(treap==nullptr)
- {
- left=nullptr;
- right=nullptr;
- return;
- }
- if(treap->key<key)
- {
- split(treap->right, key, treap->right, right);
- left=treap;
- }
- else
- {
- split(treap->left, key, left, treap->right);
- right=treap;
- }
- //update(treap);
- }
- void GetTree(Treap* treap)
- {
- if(treap==nullptr)
- {
- printf("null\n");
- return;
- }
- printf("%lld %lld\n", treap->key, treap->priority);
- GetTree(treap->left);
- GetTree(treap->right);
- }
- int main()
- {
- long long k,p,n;
- scanf("%lld", &n);
- Treap* treap=nullptr;
- for(int i=0;i<n;i++)
- {
- scanf("%lld%lld", &k,&p);
- Treap* node=new Treap;
- node->key=k;
- node->priority=p;
- Treap* left=nullptr;
- Treap* right=nullptr;
- split(treap, k, left,right);
- treap=merge(left, merge(node, right));
- }
- GetTree(treap);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement