ulvis.paste.net

Paste Search Dynamic
Recent pastes
cplusplus struct
  1. //#include "stdafx.h"
  2.  
  3. #include <algorithm>
  4. #include <string>
  5. #include <iostream>
  6. #include <vector>
  7. #include <stack>
  8.  
  9. using namespace std;
  10.  
  11. struct node
  12. {
  13.         node *l, *r;
  14.         int key, priority;
  15.         int size;
  16.         int father;
  17.         int num;
  18.         node(int new_key, int pr,int i)
  19.         {
  20.                 size = 1;
  21.                 l = nullptr;
  22.                 r = nullptr;
  23.                 father = 0;
  24.                 num = i;
  25.                 key = new_key;
  26.                 priority = pr;
  27.         }
  28.  
  29.  
  30. };
  31.  
  32. bool cmp(node* v1, node* v2)
  33. {
  34.         return v1->key < v2->key;
  35. }
  36. int size(node* v)
  37. {
  38.         if (v == nullptr)
  39.                 return 0;
  40.         return v->size;
  41. }
  42.  
  43. void upd(node* v)
  44. {
  45.         if (v == nullptr)
  46.                 return;
  47.         v->size = size(v->l) + size(v->r) + 1;
  48.         if (v->l != nullptr)
  49.                 v->l->father = v->num;
  50.         if (v->r != nullptr)
  51.                 v->r->father = v->num;
  52. }
  53.  
  54. node* merge(node *root1, node *root2)
  55. {
  56.         if (root1 == nullptr)
  57.                 return root2;
  58.         if (root2 == nullptr)
  59.                 return root1;
  60.         if (root1->priority > root2->priority)
  61.         {
  62.                 root1->r = merge(root1->r, root2);
  63.                 upd(root1);
  64.                 return root1;
  65.         }
  66.         else
  67.         {
  68.                 root2->l = merge(root1, root2->l);
  69.                 upd(root2);
  70.                 return root2;
  71.         }
  72. }
  73.  
  74. pair<node*, node*> split(node* root, int k)
  75. {
  76.         if (root == nullptr)
  77.                 return{ nullptr,nullptr };
  78.         if (root->key < k)
  79.         {
  80.                 pair<node*, node*> p = split(root->r, k);
  81.                 root->r = p.first;
  82.                 upd(root);
  83.                 return{ root,p.second };
  84.         }
  85.         else
  86.         {
  87.                 pair<node*, node*> p = split(root->l, k);
  88.                 root->l = p.second;
  89.                 upd(root);
  90.                 return{ p.first,root };
  91.         }
  92. }
  93.  
  94. node* insert(node* root, node* v)
  95. {
  96.         if (root == nullptr)
  97.                 return v;
  98.         if (v == nullptr)
  99.                 return root;
  100.         if (v->priority > root->priority)
  101.         {
  102.                 pair<node*, node*> p = split(root, v->key);
  103.                 v->l = p.first;
  104.                 v->r = p.second;
  105.                 upd(v);
  106.                 return v;
  107.         }
  108.  
  109.         if (v->key < root->key)
  110.                 root->l = insert(root->l, v);
  111.         else
  112.                 root->r = insert(root->r, v);
  113.         upd(root);
  114.         return root;
  115. }
  116.  
  117. node* erase(node* root, int key)
  118. {
  119.         if (root == nullptr)
  120.                 return root;
  121.  
  122.         if (root->key == key)
  123.                 return merge(root->l, root->r);
  124.  
  125.         if (key < root->key)
  126.                 root->l = erase(root->l, key);
  127.         else
  128.                 root->r = erase(root->r, key);
  129.         upd(root);
  130.  
  131.         return root;
  132. }
  133.  
  134.  
  135.  
  136. pair<node*, node*> split2(node* root, int cnt)
  137. {
  138.         if (root == nullptr)
  139.                 return{ nullptr,nullptr };
  140.  
  141.         if (size(root->l) + 1 <= cnt)
  142.         {
  143.                 pair<node*, node*>p = split2(root->r, cnt - size(root->l) - 1);
  144.                 root->r = p.first;
  145.                 upd(root);
  146.                 return{ root,p.second };
  147.         }
  148.         else
  149.         {
  150.                 pair<node*, node*> p = split2(root->l, cnt);
  151.                 root->l = p.second;
  152.                 upd(root);
  153.                 return{ p.first,root };
  154.         }
  155. };
  156.  
  157. bool find(node* root, int key) {
  158.         if (root == nullptr)
  159.                 return 0;
  160.         if (root->key < key)
  161.                 return find(root->r, key);
  162.         if (root->key > key)
  163.                 return find(root->l, key);
  164.  
  165.         return 1;
  166. }
  167.  
  168. void show(node* root)
  169. {
  170.         if (root == nullptr)
  171.                 return;
  172.         //cout <<
  173. }
  174.  
  175. int main()
  176. {
  177.         //freopen("input.txt", "r", stdin);
  178.         int n;
  179.         cin >> n;
  180.         vector <node*> tree,order;
  181.  
  182.         for (int i = 0; i < n; ++i)
  183.         {
  184.                 int new_key, pr;
  185.                 cin >> new_key >> pr;
  186.                 node* tmp = new node(new_key,pr,i + 1);
  187.                 tree.push_back(tmp);
  188.                 order.push_back(tree[i]);
  189.         }
  190.         sort(tree.begin(), tree.end(), cmp);
  191.  
  192.         stack <node*> st;
  193.         node* last = nullptr;
  194.         cout << "YES"<<endl;
  195.         for (int i = 0; i < n; ++i)
  196.         {
  197.                 while (!st.empty())
  198.                         if (st.top()->priority < tree[i]->priority)
  199.                                 break;
  200.                         else
  201.                         {
  202.                                 last = st.top();
  203.                                 st.pop();
  204.                         }
  205.                 tree[i]->l = last;
  206.                 upd(tree[i]);
  207.                 if (!st.empty())
  208.                 {
  209.                         st.top()->r = tree[i];
  210.                         upd(st.top());
  211.                 }
  212.                 st.push(tree[i]);
  213.                 last = nullptr;
  214.         }
  215.  
  216.         for (int i = 0; i < n; ++i)
  217.         {
  218.                 cout << order[i]->father << " ";
  219.                 if (order[i]->l == nullptr)
  220.                         cout << 0 << " ";
  221.                 else
  222.                         cout << order[i]->l->num << " ";
  223.  
  224.                 if (order[i]->r == nullptr)
  225.                         cout << 0 << endl;
  226.                 else
  227.                         cout << order[i]->r->num << endl;
  228.  
  229.  
  230.         }
  231.  
  232.  
  233. }
  234.  
Parsed in 0.050 seconds