fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4.  
  5. // PART I: AVL Tree Implementation
  6.  
  7. class range_node;
  8. class internal_node;
  9. class leaf_node;
  10.  
  11. class range_node {
  12. public:
  13.     range_node(int value, int height = 0, internal_node *parent = nullptr) : value{value}, height{height}, parent{parent} {}
  14.     range_node(int value, internal_node *parent = nullptr) : range_node{value, 0, parent} {}
  15.     virtual ~range_node() {}
  16.  
  17.     virtual bool is_leaf() = 0;
  18.     virtual int get_start() = 0;
  19.     virtual int get_end() = 0;
  20.  
  21.     int value;
  22.     int height;
  23.     internal_node *parent;
  24. };
  25.  
  26. class internal_node : public range_node {
  27. public:
  28.     internal_node(int start, int end, int value, internal_node *parent = nullptr)
  29.         : range_node{value, 1, parent}, start{start}, end{end} {}
  30.     ~internal_node() {}
  31.  
  32.     bool is_leaf() override { return false; }
  33.     int get_start() override { return start; }
  34.     int get_end() override { return end; }
  35.  
  36.     int start, end;
  37.     range_node *left{nullptr};
  38.     range_node *right{nullptr};
  39. };
  40.  
  41. class leaf_node : public range_node {
  42. public:
  43.     leaf_node(int key, int value, internal_node *parent = nullptr) : range_node{value, parent}, key{key} {}
  44.     ~leaf_node() {}
  45.  
  46.     bool is_leaf() override { return true; }
  47.     int get_start() override { return key; }
  48.     int get_end() override { return key; }
  49.  
  50.     int key;
  51. };
  52.  
  53. class range_tree {
  54. public:
  55.     ~range_tree() { free(root); root = nullptr; }
  56.  
  57.     int max() {
  58.         range_node *curr = root;
  59.         while (!curr->is_leaf()) {
  60.             curr = dynamic_cast<internal_node*>(curr)->right;
  61.         }
  62.         return curr->get_end();
  63.     }
  64.  
  65.     void insert(int key, int value) {
  66.         if (!root) {
  67.             insert_root(key, value); return;
  68.         }
  69.         if (root && !root->right) {
  70.             insert_root_child(key, value); return;
  71.         }
  72.  
  73.         auto leaf = get_leaf(key, value);
  74.         if (key == leaf->key) {
  75.             update_values(value, leaf); return;
  76.         }
  77.  
  78.         internal_node *new_node = insert_new_leaf(key, value, leaf);
  79.         update_tree(new_node->parent, new_node);
  80.     }
  81.  
  82.     int count(int key) {
  83.         return count(key, root) - 1;
  84.     }
  85.  
  86.     std::vector<int> to_vector() {
  87.         std::vector<int> output;
  88.         traversal(output, root);
  89.         return output;
  90.     }
  91.  
  92. private:
  93.     void insert_root(int key, int value) {
  94.         root = new internal_node{key, key, value + 1};
  95.         root->left = new leaf_node{key, value + 1, root};
  96.     }
  97.  
  98.     void insert_root_child(int key, int value) {
  99.         if (key < root->start) {
  100.             root->right = root->left;
  101.             root->left = new leaf_node{key, value + 1, root};
  102.             root->start = key;
  103.             root->value = (value + 1) * root->right->value;
  104.             return;
  105.         } else if (key > root->start) {
  106.             root->right = new leaf_node{key, value + 1, root};
  107.             root->end = key;
  108.             root->value = (value + 1) * root->left->value;
  109.         } else {
  110.             root->left->value += value;
  111.             root->value += value;
  112.         }
  113.     }
  114.  
  115.     leaf_node* get_leaf(int key, int value) {
  116.         range_node *curr_node = root;
  117.         internal_node *curr = nullptr;
  118.  
  119.         while (!curr_node->is_leaf()) {
  120.             curr = dynamic_cast<internal_node*>(curr_node);
  121.             if (key <= curr->left->get_end())
  122.                 curr_node = curr->left;
  123.             else
  124.                 curr_node = curr->right;
  125.         }
  126.  
  127.         return dynamic_cast<leaf_node*>(curr_node);
  128.     }
  129.  
  130.     void update_values(int value, leaf_node *leaf) {
  131.         leaf->value += value;
  132.         auto p = leaf->parent;
  133.         while (!p) {
  134.             p->value = p->left->value * p->right->value;
  135.             p = p->parent;
  136.         }
  137.     }
  138.  
  139.     internal_node* insert_new_leaf(int key, int value, leaf_node *leaf) {
  140.         internal_node *new_node;
  141.  
  142.         if (key > leaf->key) {
  143.             new_node = new internal_node{leaf->key, key, (value + 1) * leaf->value};
  144.             new_node->left = leaf;
  145.             new_node->right = new leaf_node{key, value + 1, new_node};
  146.         } else {
  147.             new_node = new internal_node{key, leaf->key, (value + 1) * leaf->value};
  148.             new_node->left = new leaf_node{key, value + 1, new_node};
  149.             new_node->right = leaf;
  150.         }
  151.  
  152.         new_node->parent = leaf->parent;
  153.         leaf->parent = new_node;
  154.  
  155.         if (new_node->parent->left == leaf) {
  156.             new_node->parent->left = new_node;
  157.         } else {
  158.             new_node->parent->right = new_node;
  159.         }
  160.  
  161.         return new_node;
  162.     }
  163.  
  164.     void update_tree(internal_node *curr, internal_node *new_node) {
  165.         internal_node *parent;
  166.         bool is_left;
  167.  
  168.         while (curr) {
  169.             update_node(curr);
  170.             parent = curr->parent;
  171.             is_left = parent ? (parent->left == curr) : false;
  172.  
  173.             curr = rebalance(curr, new_node);
  174.  
  175.             if (!parent) {
  176.                 root = curr;
  177.                 root->parent = nullptr;
  178.             } else {
  179.                 if (is_left) parent->left = curr;
  180.                 else parent->right = curr;
  181.                 curr->parent = parent;
  182.             }
  183.  
  184.             curr = parent;
  185.         }
  186.     }
  187.  
  188.     internal_node* rebalance(internal_node *curr, internal_node *new_node) {
  189.         int balance = curr->left->height - curr->right->height;
  190.  
  191.         if (balance > 1) {
  192.             curr = left_left_case(curr, new_node);
  193.             curr = left_right_case(curr, new_node);
  194.         }
  195.  
  196.         if (balance < -1) {
  197.             curr = right_right_case(curr, new_node);
  198.             curr = right_left_case(curr, new_node);
  199.         }
  200.  
  201.         return curr;
  202.     }
  203.  
  204.     internal_node* left_left_case(internal_node *curr, internal_node *new_node) {
  205.         internal_node *prev = dynamic_cast<internal_node*>(curr->left);
  206.         if (prev) {
  207.             internal_node *temp = dynamic_cast<internal_node*>(prev->left);
  208.             if (temp && new_node->start >= temp->start && new_node->end <= temp->end) {
  209.                 return rotate_right(curr, prev);
  210.             }
  211.         }
  212.         return curr;
  213.     }
  214.  
  215.     internal_node* left_right_case(internal_node *curr, internal_node *new_node) {
  216.         internal_node *prev = dynamic_cast<internal_node*>(curr->left);
  217.         if (prev) {
  218.             internal_node *temp = dynamic_cast<internal_node*>(prev->right);
  219.             if (temp && new_node->start >= temp->start && new_node->end <= temp->end) {
  220.                 prev = rotate_left(prev, temp);
  221.                 return rotate_right(curr, prev);
  222.             }
  223.         }
  224.         return curr;
  225.     }
  226.  
  227.     internal_node* right_right_case(internal_node *curr, internal_node *new_node) {
  228.         internal_node *prev = dynamic_cast<internal_node*>(curr->right);
  229.         if (prev) {
  230.             internal_node *temp = dynamic_cast<internal_node*>(prev->right);
  231.             if (temp && new_node->start >= temp->start && new_node->end <= temp->end) {
  232.                 return rotate_left(curr, prev);
  233.             }
  234.         }
  235.         return curr;
  236.     }
  237.  
  238.     internal_node* right_left_case(internal_node *curr, internal_node *new_node) {
  239.         internal_node *prev = dynamic_cast<internal_node*>(curr->right);
  240.         if (prev) {
  241.             internal_node *temp = dynamic_cast<internal_node*>(prev->left);
  242.             if (temp && new_node->start >= temp->start && new_node->end <= temp->end) {
  243.                 prev = rotate_right(prev, temp);
  244.                 return rotate_left(curr, prev);
  245.             }
  246.         }
  247.         return curr;
  248.     }
  249.  
  250.     internal_node* rotate_right(internal_node *curr, internal_node *prev) {
  251.         curr->left = prev->right;
  252.         prev->right = curr;
  253.         curr->parent = prev;
  254.         curr->left->parent = curr;
  255.  
  256.         update_node(curr);
  257.         update_node(prev);
  258.  
  259.         return prev;
  260.     }
  261.  
  262.     internal_node* rotate_left(internal_node *curr, internal_node *prev) {
  263.         curr->right = prev->left;
  264.         prev->left = curr;
  265.         curr->parent = prev;
  266.         curr->right->parent = curr;
  267.  
  268.         update_node(curr);
  269.         update_node(prev);
  270.  
  271.         return prev;
  272.     }
  273.  
  274.     void update_node(internal_node *p) {
  275.         p->start = p->left->get_start();
  276.         p->end = p->right->get_end();
  277.         p->value = p->left->value * p->right->value;
  278.         p->height = std::max(p->left->height, p->right->height) + 1;
  279.     }
  280.  
  281.     int count(int key, range_node *node) {
  282.         if (!node) return 1;
  283.  
  284.         if (node->is_leaf()) {
  285.             auto leaf = dynamic_cast<leaf_node*>(node);
  286.             if (key >= leaf->key) {
  287.                 return leaf->value;
  288.             }
  289.             return 1;
  290.         }
  291.  
  292.         auto internal = dynamic_cast<internal_node*>(node);
  293.  
  294.         if (key < internal->right->get_start()) {
  295.             return count(key, internal->left);
  296.         }
  297.  
  298.         if (key < internal->right->get_end()) {
  299.             return internal->left->value * count(key, internal->right);
  300.         }
  301.  
  302.         return internal->value;
  303.     }
  304.  
  305.     void traversal(std::vector<int> &output, range_node *node) {
  306.         if (!node) return;
  307.  
  308.         if (node->is_leaf()) {
  309.             auto leaf = dynamic_cast<leaf_node*>(node);
  310.             for (int i = 0; i < leaf->value-1; i++)
  311.                 output.push_back(leaf->key);
  312.             return;
  313.         }
  314.  
  315.         auto p = dynamic_cast<internal_node*>(node);
  316.         traversal(output, p->left);
  317.         traversal(output, p->right);
  318.     }
  319.  
  320.     void free(range_node *node) {
  321.         if (!node) return;
  322.  
  323.         auto internal = dynamic_cast<internal_node*>(node);
  324.         if (internal) {
  325.             free(internal->left);
  326.             free(internal->right);
  327.         }
  328.  
  329.         delete node;
  330.     }
  331.  
  332.     internal_node *root{nullptr};
  333. };
  334.  
  335. // PART II: Solution
  336.  
  337. typedef std::vector<std::pair<int,int>> pair_array;
  338.  
  339. pair_array make_pair_sequence(const std::vector<int> &numbers) {
  340.     pair_array arr;
  341.  
  342.     for (int i = 0; i < numbers.size(); i++) {
  343.         if (i == 0) {
  344.             arr.push_back(std::make_pair(numbers[i], 1));
  345.         } else if (arr[arr.size()-1].first != numbers[i]) {
  346.             arr.push_back(std::make_pair(numbers[i], 1));
  347.         } else {
  348.             arr[arr.size()-1].second++;
  349.         }
  350.     }
  351.  
  352.     return arr;
  353. }
  354.  
  355. int decreasing_sequence_last_index(const pair_array &arr) {
  356.     int index = 0;
  357.     while (index < arr.size()-1 &&
  358.            arr[index].first > arr[index+1].first) {
  359.         index++;
  360.     }
  361.     return index;
  362. }
  363.  
  364. int increasing_sequence_last_index(const pair_array &arr) {
  365.     int index = 0;
  366.     while (index < arr.size()-1 &&
  367.            arr[index].first < arr[index+1].first) {
  368.         index++;
  369.     }
  370.     return index;
  371. }
  372.  
  373. int solution_sort(const std::vector<int> &numbers, bool debug) {
  374.     pair_array arr = make_pair_sequence(numbers);
  375.  
  376.     if (arr.size() < 2) {
  377.         return 0;
  378.     }
  379.  
  380.     range_tree tree;
  381.     int count = 0;
  382.  
  383.     int last_index = decreasing_sequence_last_index(arr);
  384.     if (last_index > 0) {
  385.         tree.insert(arr[0].first, arr[0].second);
  386.         for (int i = 1; i <= last_index; i++) {
  387.             count += arr[i].second;
  388.             tree.insert(arr[i].first, arr[i].second);
  389.         }
  390.     }
  391.  
  392.     if (last_index == 0) {
  393.         last_index = increasing_sequence_last_index(arr);
  394.         for (int i = 0; i <= last_index; i++) {
  395.             tree.insert(arr[i].first, arr[i].second);
  396.         }
  397.     }
  398.  
  399.     for (int i = last_index+1; i < arr.size(); i++) {
  400.         if (arr[i].first < tree.max()) {
  401.             count += arr[i].second;
  402.             count += tree.count(arr[i].first);
  403.             tree.insert(arr[i].first, arr[i].second);
  404.         }
  405.     }
  406.  
  407.     if (debug) {
  408.         std::vector<int> output = tree.to_vector();
  409.         for (auto e : output) std::cout << e << " ";
  410.         std::cout << "\n";
  411.     }
  412.  
  413.     return count;
  414. }
  415.  
  416. int main() {
  417.     int size; std::cin >> size;
  418.  
  419.     std::vector<int> numbers(size);
  420.     for (int i = 0; i < size; i++) std::cin >> numbers[i];
  421.  
  422.     int count = solution_sort(numbers, true);
  423.     std::cout << count << std::endl;
  424. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
6
5 1 1 2 4 3
stdout
copy 
1 1 2 3 4 5 
17
https://ideone.com/X57kOd
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!