daily pastebin goal
17%
SHARE
TWEET

Untitled

a guest Apr 16th, 2018 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<string>
  5. #include<iomanip>
  6. #include<cmath>
  7.  
  8. using namespace std;
  9.  
  10. struct Node {
  11.     Node* left;
  12.     Node* right;
  13.     int r, b, mr, mb;
  14.     int cnt, y, ind;
  15. };
  16.  
  17. int getR(Node* node) {
  18.     if (!node) {
  19.         return 0;
  20.     }
  21.     return node->mr;
  22. }
  23.  
  24. int getB(Node* node) {
  25.     if (!node) {
  26.         return 0;
  27.     }
  28.     return node->mb;
  29. }
  30.  
  31. int getCnt(Node* node) {
  32.     if (!node) {
  33.         return 0;
  34.     }
  35.     return node->cnt;
  36. }
  37.  
  38. void update(Node* node) {
  39.     node->mr = max(getR(node->left), getR(node->right));
  40.     node->mb = max(getB(node->left), getB(node->right));
  41.     node->cnt = getCnt(node->left) + getCnt(node->right) + 1;
  42. }
  43.  
  44. pair<Node*, Node*> SplitRed(Node* node, int x) {
  45.     if (!node) {
  46.         return{ nullptr, nullptr };
  47.     }
  48.     pair<Node*, Node*> now;
  49.     if (node->mr > x) {
  50.         now = SplitRed(node->left, x);
  51.         node->left = now.second;
  52.         now.second = node;
  53.         update(now.second);
  54.     }
  55.     else {
  56.         now = SplitRed(node->right, x);
  57.         node->right = now.first;
  58.         now.first = node;
  59.         update(now.first);
  60.     }
  61.     return now;
  62. }
  63.  
  64. pair<Node*, Node*> SplitBlue(Node* node, int x) {
  65.     if (!node) {
  66.         return{ nullptr, nullptr };
  67.     }
  68.     pair<Node*, Node*> now;
  69.     if (node->mb > x) {
  70.         now = SplitBlue(node->left, x);
  71.         node->left = now.second;
  72.         now.second = node;
  73.         update(now.second);
  74.     }
  75.     else {
  76.         now = SplitBlue(node->right, x);
  77.         node->right = now.first;
  78.         now.first = node;
  79.         update(now.first);
  80.     }
  81.     return now;
  82. }
  83.  
  84. Node* Merge(Node* L, Node* R) {
  85.     if (!L) {
  86.         return R;
  87.     }
  88.     if (!R) {
  89.         return L;
  90.     }
  91.     if (L->y > R->y) {
  92.         L->right = Merge(L->right, R);
  93.         update(L);
  94.         return L;
  95.     }
  96.     R->left = Merge(L, R->left);
  97.     update(R);
  98.     return R;
  99. }
  100.  
  101. Node* InsertRed(Node* root, int r, int b, int ind) {
  102.     pair<Node*, Node*> p1;
  103.     p1 = SplitRed(root, r);
  104.     Node* node = new Node{ nullptr, nullptr, r, b, r, b, 1, rand(), ind };
  105.     p1.first = Merge(p1.first, node);
  106.     root = Merge(p1.first, p1.second);
  107.     return root;
  108. }
  109.  
  110. Node* InsertBlue(Node* root, int r, int b, int ind) {
  111.     pair<Node*, Node*> p1;
  112.     p1 = SplitBlue(root, b);
  113.     Node* node = new Node{ nullptr, nullptr, r, b, r, b, 1, rand(), ind };
  114.     p1.first = Merge(p1.first, node);
  115.     root = Merge(p1.first, p1.second);
  116.     return root;
  117. }
  118.  
  119. void print(Node* node, vector<int> &v, int now) {
  120.     //vector<int> v(n);
  121.     if (!node) {
  122.         return;
  123.     }
  124.     v[getCnt(node->left) + now] = node->ind ;
  125.     print(node->left, v, now);
  126.     print(node->right, v, now + getCnt(node->left) + 1);
  127. }
  128.  
  129. int main() {
  130.     srand(228);
  131.     int n;
  132.     cin >> n;
  133.     Node* root = nullptr;
  134.     for (int i = 0; i < n; ++i) {
  135.         int r, b, type;
  136.         cin >> r >> b >> type;
  137.         if (type == 1) {
  138.             root = InsertRed(root, r, b, i);
  139.         }
  140.         else {
  141.             root = InsertBlue(root, r, b, i);
  142.         }
  143.     }
  144.     vector<int> v(n);
  145.     print(root, v, 0);
  146.     for (int i = 0; i < n; ++i) {
  147.         cout << v[i] + 1 << " ";
  148.     }
  149.     return 0;
  150. }
RAW Paste Data
Top