• API
• FAQ
• Tools
• Archive
daily pastebin goal
39%
SHARE
TWEET

# Untitled

a guest Apr 16th, 2018 56 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top