Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- struct Node {
- int dataFirst;
- int dataSecond;
- long long ln = 1ll;
- Node * left = nullptr;
- Node * right = nullptr;
- };
- struct Pair {
- Node * first;
- Node * second;
- };
- Node * root;
- int size_ = 0;
- int getSum(Node * current) {
- if (current == NULL) {
- return 0;
- } else {
- return current -> ln;
- }
- }
- void qSort(int **arr, int nStart, int nEnd) {
- int l, r, x;
- if (nStart >= nEnd) return;
- l = nStart;
- r = nEnd;
- x = arr[(l + r) / 2][1];
- while (l <= r) {
- while (arr[l][1] < x) l++;
- while (arr[r][1] > x) r--;
- if (l <= r) {
- int first = arr[l][0];
- int second = arr[l][1];
- arr[l][0] = arr[r][0];
- arr[r][0] = first;
- arr[l][1] = arr[r][1];
- arr[r][1] = second;
- }
- l++;
- r--;
- }
- qSort(arr, nStart, r);
- qSort(arr, l, nEnd);
- }
- void update(Node * root) {
- if (root == NULL) {
- return;
- } else {
- root -> ln = 1 + getSum(root -> left) + getSum(root -> right);
- }
- }
- Node * merge(Node * first, Node * second) {
- if (first == NULL || second == NULL) {
- return first == NULL ? second : first;
- } else {
- if (first -> dataSecond > second -> dataSecond) {
- first -> right = merge(first -> right, second);
- update(first);
- return first;
- } else {
- second -> left = merge(first, second -> left);
- update(second);
- return second;
- }
- }
- }
- Pair split(Node * root, int value) {
- Pair pair;
- if (root == NULL) {
- pair.first = NULL;
- pair.second = NULL;
- return pair;
- } else {
- if (root -> dataFirst < value) {
- pair = split(root -> right, value);
- root -> right = pair.first;
- pair.first = root;
- } else {
- pair = split(root -> left, value);
- root -> left = pair.second;
- pair.second = root;
- }
- }
- update(pair.first);
- update(pair.second);
- return pair;
- }
- void insert(int dataFirst, int dataSecond) {
- Node * forInsert = new Node();
- forInsert -> dataFirst = dataFirst;
- forInsert -> dataSecond = dataSecond;
- Pair pair;
- pair = split(root, dataFirst);
- pair.first = merge(pair.first, forInsert);
- root = merge(pair.first, pair.second);
- size_++;
- }
- void inOrderTraversal(Node * root, Node * currentParent) {
- if (root != nullptr) {
- inOrderTraversal(root -> left, root);
- if (currentParent != nullptr) {
- cout << currentParent -> dataFirst << " ";
- } else {
- cout << 0 << " ";
- }
- if (root -> left != nullptr) {
- cout << root -> left -> dataFirst << " ";
- } else {
- cout << 0 << " ";
- }
- if (root -> right != nullptr) {
- cout << root -> right -> dataFirst << " ";
- } else {
- cout << 0 << " ";
- }
- cout << endl;
- inOrderTraversal(root -> right, root);
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin >> n;
- int **arr;
- arr = new int*[n];
- for (int i = 0; i < n; i++) {
- int x, y;
- cin >> x >> y;
- arr[i] = new int[2];
- arr[i][0] = x;
- arr[i][1] = y;
- }
- /*for (int i = 0; i < n; i++) {
- cout << arr[i][0] << " " << arr[i][1] << endl;
- }*/
- qSort(arr, 0, n - 1);
- /*for (int i = 0; i < n; i++) {
- cout << arr[i][0] << " " << arr[i][1] << endl;
- }
- cout << endl;*/
- for(int i = 0; i < n; i++) {
- insert(arr[n - 1 - i][0], arr[i][1]);
- }
- inOrderTraversal(root, nullptr);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement