Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 28th, 2020 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<vector>
  3. const int MAX_NUM = 100000;
  4.  
  5. #define $$ std::cout << std::endl << "-----------------" << std::endl;
  6. //#define sorted rev_sorted
  7. //#define rev_sorted sorted
  8.  
  9. int tree_min = 1000'000'000;
  10. int min_ind = 0;
  11.  
  12. int random_(){
  13.     return (std::rand()<<14) + 5 * std::rand();
  14. }
  15.  
  16. struct Node{
  17.     Node* left;
  18.     Node* right;
  19.     bool rev;
  20.     int dop;
  21.     int x;
  22.     int y;
  23.     int sz;
  24.     int sum;
  25.     int assig;
  26.     int mx;
  27.     int mn;
  28.     bool sorted;
  29.     bool rev_sorted;
  30.     Node(int _x){
  31.         x = _x;
  32.         y = random_();
  33.         dop = 0;
  34.         rev = 0;
  35.         sorted = 1;
  36.         sz = 1;
  37.         sum = x;
  38.         assig = MAX_NUM;
  39.         mx = _x;
  40.         mn = _x;
  41.         sorted = 1;
  42.         rev_sorted = 1;
  43.         left = nullptr;
  44.         right = nullptr;
  45.     }
  46. };
  47.  
  48. class Pivo{
  49.     private:
  50.         Node* root = nullptr;
  51.  
  52.         static int size_(Node* &tree){
  53.             return tree == nullptr ? 0 : tree->sz;
  54.         }
  55.  
  56.         static void push_dop(Node* &tree){
  57.             if (tree->dop == 0){
  58.                 return;
  59.             }
  60.             if (tree->left != nullptr){
  61.                 tree->left->dop += tree->dop;
  62.             }
  63.             if (tree->right != nullptr){
  64.                 tree->right->dop += tree->dop;
  65.             }
  66.             tree->sum += (tree->dop) * size_(tree);
  67.             tree->x += tree->dop;
  68.             tree->mx += tree->dop;
  69.             tree->mn += tree->dop;
  70.  
  71.             //std::cout << "aaaaaaaaaaaaaaaaaaaaaaaa\n" << size_(tree) << ' ' << tree->dop << ' ' << tree->sum <<  "\nbbbbbbbbbbbbbbbbbbbbbbbbbb\n";
  72.             tree->dop = 0;
  73.         }
  74.  
  75.         static void push_assign(Node* &tree){
  76.             if (tree->assig == MAX_NUM){
  77.                 return;
  78.             }
  79.             if (tree->left != nullptr){
  80.                 tree->left->assig = tree->assig;
  81.                 tree->left->dop = 0;
  82.             }
  83.             if (tree->right != nullptr){
  84.                 tree->right->assig = tree->assig;
  85.                 tree->right->dop = 0;
  86.             }
  87.             tree->x = tree->assig;
  88.             tree->sum = tree->assig * size_(tree);
  89.             tree->mx = tree->assig;
  90.             tree->mn = tree->assig;
  91.             tree->sorted = 1;
  92.             tree->rev_sorted = 1;
  93.             tree->assig = MAX_NUM;
  94.             tree->dop = 0;
  95.         }
  96.  
  97.         static void push_rev(Node* &tree){
  98.             if (!tree->rev){
  99.                 return;
  100.             }
  101.             if (tree->left != nullptr){
  102.                 tree->left->rev ^= 1;
  103.             }
  104.             if (tree->right != nullptr){
  105.                 tree->right->rev ^= 1;
  106.             }
  107.             std::swap(tree->right, tree->left);
  108.             if (tree->sorted && !tree->rev_sorted || !tree->sorted && tree->rev_sorted){
  109.             //if (tree->sorted ^ tree->rev_sorted){
  110.                 tree->sorted ^= 1;
  111.                 tree->rev_sorted ^= 1;
  112.             }
  113.             tree->rev = 0;
  114.         }
  115.  
  116.         static void push(Node* &tree){
  117.             if(tree == nullptr){
  118.                 return;
  119.             }
  120.             push_assign(tree);
  121.             push_dop(tree);
  122.             push_rev(tree);
  123.         }
  124.  
  125.         static void update(Node* &tree){
  126.             if (tree == nullptr){
  127.                 return;
  128.             }
  129.             push(tree->left);
  130.             push(tree->right);
  131.             int sm1 = 0;
  132.             int sm2 = 0;
  133.             tree->mx = tree->x;
  134.             tree->mn = tree->x;
  135.             tree->sz = size_(tree->left) + size_(tree->right) + 1;
  136.             if (tree->left != nullptr){
  137.                 sm1 = tree->left->sum;
  138.                 tree->mx = std::max(tree->mx, tree->left->mx);
  139.                 tree->mn = std::min(tree->mn, tree->left->mn);
  140.             }
  141.             if (tree->right != nullptr){
  142.                 sm2 = tree->right->sum;
  143.                 tree->mx = std::max(tree->mx, tree->right->mx);
  144.                 tree->mn = std::min(tree->mn, tree->right->mn);
  145.             }
  146.             if ((tree->right != nullptr) && (tree->left != nullptr)){
  147.                //     std::cout << "ya dolbaeb\n";
  148.                 //std::cout << tree->left->x << ' ' << tree->left->mx << ' ' << tree->x << ' ' << tree->right->x << ' ' << tree->right->mx << std::endl;
  149.                 tree->sorted = tree->left->sorted && tree->right->sorted && tree->left->mx <= tree->x && tree->x <= tree->right->mn ? 1 : 0;
  150.                 tree->rev_sorted = (tree->left->rev_sorted) && (tree->right->rev_sorted) && (tree->left->mn <= tree->x) && (tree->x >= tree->right->mx) ? 1 : 0;
  151.             } else if (tree->left != nullptr){
  152.                 //std::cout << "ya dolbaeb2\n";
  153.                 tree->sorted = tree->left->sorted && tree->x >= tree->left->mn ? 1 : 0;
  154.                 tree->rev_sorted = tree->left->rev_sorted && tree->x <= tree->left->mn ? 1 : 0;
  155.             } else if (tree->right != nullptr){
  156.                 //std::cout << "ya dolbaeb3\n";
  157.                 tree->sorted = tree->right->sorted && tree->x <= tree->right->mn ? 1 : 0;
  158.                 tree->rev_sorted = tree->right->rev_sorted && tree->x >= tree->right->mx ? 1 : 0;
  159.             } else {
  160.                 //std::cout << "ya dolbaeb4\n";
  161.                 tree->sorted = 1;
  162.                 tree->rev_sorted = 1;
  163.             }
  164.             tree->sum = tree->x + sm1 + sm2;
  165.         }
  166.         static Node* merge_(Node* &f_tree, Node* &s_tree){
  167.             push(f_tree);
  168.             push(s_tree);
  169.             //std::cout << "************" << std::endl;
  170.             if (f_tree == nullptr){
  171.                  //   std::cout << "govno" << std::endl;
  172.                 return s_tree;
  173.             }
  174.             if (s_tree == nullptr){
  175.                 return f_tree;
  176.             }
  177.             //std::cout << "%%%%%%%%%%%%%%%%%%" << std::endl;
  178.             if (f_tree->y > s_tree->y){
  179.                 f_tree->right = merge_(f_tree->right, s_tree);
  180.                 update(f_tree);
  181.                 return f_tree;
  182.             } else {
  183.                 s_tree->left = merge_(f_tree, s_tree->left);
  184.                 update(s_tree);
  185.                 return s_tree;
  186.             }
  187.         }
  188.         static std::pair<Node*, Node*> split(Node* &tree, int key){
  189.             push(tree);
  190.             if (tree == nullptr){
  191.                 return {nullptr, nullptr};
  192.             }
  193.             if(size_(tree->left) < key){
  194.                 std::pair<Node*, Node*> trees = split(tree->right, key - size_(tree->left) - 1);
  195.                 tree->right = trees.first;
  196.                 update(tree);
  197.                 return {tree, trees.second};
  198.             } else {
  199.                 std::pair<Node*, Node*> trees = split(tree->left, key);
  200.                 tree->left = trees.second;
  201.                 update(tree);
  202.                 return {trees.first, tree};
  203.             }
  204.         }
  205.  
  206.     public:
  207.         static int descent(Node* &tree, int suff_max){
  208.             if (tree == nullptr){
  209.                 return -INT_MAX;
  210.             }
  211.             push(tree->left);
  212.             push(tree->right);
  213.           //  if (tree->rev_sorted){
  214.           //      return size_(tree);
  215.           //  }
  216.             std::cout << "tree: "; print_(tree); std::cout << std::endl;
  217.             if (tree->left != nullptr){
  218.                 std::cout << "left:\n";
  219.                 print_(tree->left);
  220.                 std::cout << std::endl << ' ' << tree->left->sorted << ' ' << tree->left->rev_sorted << std::endl;
  221.             } else {
  222.                 std::cout << "No left\n";
  223.             }
  224.             if (tree->right != nullptr){
  225.                 std::cout << "right:\n";
  226.                 print_(tree->right);
  227.                 std::cout << std::endl << ' ' << tree->right->sorted << ' ' << tree->right->rev_sorted << std::endl;
  228.             } else {
  229.                 std::cout << "No right\n";
  230.             }
  231.            /* if (!tree->right || tree->right->rev_sorted){
  232.                 return descent(tree->left) + size_(tree->right) + 1;
  233.             } else {
  234.                 descent(tree->right);
  235.             }*/
  236.  
  237.             /*if (tree->right != nullptr && tree->right->rev_sorted && tree->x >= tree->right->mx){
  238.                 return descent(tree->left) + size_(tree->right) + 1;
  239.             } else if (tree->right != nullptr && tree->right->rev_sorted){
  240.                 return size_(tree->right) + 1;
  241.             } else {
  242.                 return descent(tree->right);
  243.             }*/
  244.             //if (tree->right != nullptr && tree->x == tree->right->x){
  245.             //    tree->
  246.             //}
  247.             std::cout << "suff_max: " << suff_max << std::endl;
  248.             if (tree->right != nullptr && !(tree->right->rev_sorted)){
  249.                 std::cout << "eshkere\n";
  250.                 return descent(tree->right, suff_max);
  251.             } else if (tree->right != nullptr && tree->right->rev_sorted){
  252.                 std::cout << "ponos\n";
  253.                 if (tree->right->mn < suff_max){
  254.                     std::cout << "sudaaaaaaaaa\n";
  255.                     return descent(tree->right, suff_max);
  256.                 }
  257.                 if (tree->right->mx > tree->x){
  258.                     std::cout << "igor geniy" << std::endl;
  259.                     return size_(tree->right);
  260.                 }
  261.                 return descent(tree->left, tree->x) + size_(tree->right) + 1;
  262.             } else {
  263.                 if (tree->x < suff_max){
  264.                     std::cout << "igor gay" << std::endl;
  265.                     return 0;
  266.                 }
  267.                 std::cout << "igor ne gay" << ' ' << size_(tree->right) + 1 << ' ';// << descent(tree->left, tree->x) << ' ' << (tree->left == nullptr) << std::endl;
  268.                 return descent(tree->left, tree->x) + size_(tree->right) + 1;
  269.             }
  270.         }
  271.         static void upper_bound_(Node* &tree, int val, int num){
  272.             if (tree == nullptr){
  273.                 return;
  274.             }
  275.             if (tree->x <= val && tree->left != nullptr){
  276.                 upper_bound_(tree->left, val, num);// + size_(tree->left) + 1);
  277.             } else {
  278.                 if (tree_min > tree->x && tree->x > val){
  279.                     tree_min = tree->x;
  280.                     min_ind = num + size_(tree->left);// + size_(tree->left);
  281.                 }
  282.                 if (tree->right != nullptr){
  283.                     upper_bound_(tree->right, val, num + size_(tree->left) + 1);
  284.                 }
  285.             }
  286.         }
  287.         static void swap_(Node* &tree, int fir, int sec){
  288.             std::cout << "starttttttttttttttttttt\n";
  289.             std::cout << "real swap: " << fir << ' ' << sec << std::endl;
  290.             print_(tree); std::cout << std::endl;
  291.             std::pair<Node*, Node*> forest1 = split(tree, fir + 1);
  292.             std::cout << "ahuy: "; print_(forest1.first); std::cout << std::endl;
  293.             std::pair<Node*, Node*> forest2 = split(forest1.second, sec - size_(forest1.first));
  294.             Node* help_tree = merge_(forest1.first, forest2.second);
  295.             $$
  296.             print_(help_tree); std::cout << "   "; print_(forest1.first); std::cout << "   "; print_(forest2.second);
  297.             $$
  298.             //add_rev;
  299.             add_reverse(help_tree, fir, fir + 1);
  300.           //  print_(forest2.first);
  301.             std::cout << std::endl;
  302.         //add_reverse(forest2.first, 0, size_(forest2.first) - 1);
  303.             std::pair<Node*, Node*> forest3 = split(help_tree, fir + 1);
  304.             Node* help_tree2 = merge_(forest3.first, forest2.first);
  305.             std::cout << "help_tree2: "; print_(help_tree2); std::cout << std::endl;
  306.             tree = merge_(help_tree2, forest3.second);
  307.             print_(tree);
  308.             std::cout << "\nfinishhhhhhhhhhhhhhhhhh\n";
  309.         }
  310.  
  311.         static void next_permutation_(Node* &tree){
  312.             $$ print_(tree); $$
  313.             int otstup = descent(tree, -INT_MAX);
  314.             int pos = size_(tree) - otstup - 1;
  315.             std::cout << pos << ' ' << tree->sorted << ' ' << tree->rev_sorted << ' ' << otstup <<"  mocha" << std::endl;
  316.             if (otstup < 0){
  317.                 add_reverse(tree, 0, size_(tree) - 1);
  318.                 return;
  319.             }
  320.             std::pair<Node*, Node*> forest1 = split(tree, pos);
  321.             std::pair<Node*, Node*> forest2 = split(forest1.second, 1);
  322.             int val = forest2.first->x;
  323.             std::cout << val << std::endl;
  324.             Node* new_tree = forest2.second; //merge_(forest2.first, forest2.second);
  325.             tree_min = new_tree->mx + 1;
  326.             std::cout << "qqqqqqqqqqqqqqqqqqqq\n";
  327.             print_(new_tree);
  328.             std::cout << std::endl << " chlen " << tree_min << std::endl;
  329.             upper_bound_(new_tree, val, 0);
  330.             std::cout << "tree_min: " << tree_min << ' ' << min_ind << std::endl;
  331.             new_tree = merge_(forest2.first, forest2.second);
  332.             tree = merge_(forest1.first, new_tree);
  333.             std::cout << "swapaem: " << pos << ' ' << min_ind << std::endl;
  334.             swap_(tree, pos, pos + min_ind + 1);
  335.             add_reverse(tree, pos + 1, size_(tree) - 1);
  336.             //add_reverse(tree, pos + 1, pos + min_ind);
  337.         }
  338.  
  339.         static void add_val(Node* &tree, int val){
  340.             tree->dop += val;
  341.             push(tree);
  342.         }
  343.         static void ass_val(Node* &tree, int val){
  344.             tree->assig = val;
  345.             tree->dop = 0;
  346.             push(tree);
  347.         }
  348.         static void add_rev(Node* &tree, int val){
  349.             tree->rev ^= val;
  350.             push(tree);
  351.         }
  352.         static int get_sum(Node* &tree){
  353.             return tree->sum;
  354.         }
  355.         static int get_min(Node* &tree){
  356.             return tree->mn;
  357.         }
  358.         static int get_max(Node* &tree){
  359.             return tree->mx;
  360.         }
  361.         void ins(int x, int pos){
  362.             Node* new_vertex = new Node(x);
  363.             std::pair<Node*, Node*> trees = split(root, pos + 1);
  364.             Node* tree1 = merge_(trees.first, new_vertex);
  365.             root = merge_(tree1, trees.second);
  366.         }
  367.  
  368.         void del(int pos){
  369.             std::pair<Node*, Node*> trees1 = split(this->root, pos + 1);
  370.             std::pair<Node*, Node*> trees2 = split(trees1.first, pos);
  371.             this->root = merge_(trees2.first, trees1.second);
  372.         }
  373.         void operation(int val, int start, int finish, std::string type){
  374.             std::pair<Node*, Node*> forest1 = split(this->root, finish + 1);
  375.             std::pair<Node*, Node*> forest2 = split(forest1.first, start);
  376.             if (type == "add"){
  377.                 std::cout << "huy" << ' ' << val << '\n';
  378.                 add_val(forest2.second, val);
  379.             } else if (type == "rev") {
  380.                 add_rev(forest2.second, val);
  381.             } else if (type == "assign"){
  382.                 std::cout << "tut0" << std::endl;
  383.                 ass_val(forest2.second, val);
  384.             } else {
  385.                 next_permutation_(forest2.second);
  386.             }
  387.            // f(forest2.second, val);
  388.             Node* help_tree = merge_(forest2.first, forest2.second);
  389.             this->root = merge_(help_tree, forest1.second);
  390.         }
  391.  
  392.         int get(int start, int finish, std::string type){
  393.             std::pair<Node*, Node*> forest1 = split(this->root, finish + 1);
  394.             std::pair<Node*, Node*> forest2 = split(forest1.first, start);
  395.             Node* tree = forest2.second;
  396.             push(tree);
  397.           //  print_(tree);
  398.         //    std::cout << std::endl;
  399.             int answer;
  400.             if (type == "sum"){
  401.                 answer = get_sum(tree);
  402.             } else if (type == "min"){
  403.                 answer = get_min(tree);
  404.             } else {
  405.                 answer = get_max(tree);
  406.             }
  407.             Node* help_tree = merge_(forest2.first, tree);
  408.             this->root = merge_(help_tree, forest1.second);
  409.             return answer;
  410.         }
  411.         void build(std::vector<int> &s){
  412.             for (int i: s){
  413.                 Node* new_vertex = new Node(i);
  414.                 //print2(new_vertex);
  415.                 //print_(new_vertex);$$ $$
  416.                 root = merge_(root, new_vertex);
  417.                // std::cout << "jopa" << std::endl;
  418.                 //print2(root);
  419.                 //print_(root); $$
  420.             }
  421.         }
  422.         void print(){
  423.             print_(root);
  424.         }
  425.         static void print_(Node* &tree){
  426.             //
  427.             if (tree == nullptr){
  428.                 return;
  429.             }
  430.             push(tree);
  431.             //std::cout << "00000" << ' ' << (tree->left == nullptr) << ' ' << (tree->right == nullptr) << std::endl;
  432.             if (tree->left != nullptr){
  433.                 print_(tree->left);
  434.             }
  435.             //std::cout << "11111" << std::endl;
  436.             std::cout << tree->x << ' ';
  437.             //std::cout << "22222" << std::endl;
  438.             if (tree->right != nullptr){
  439.                 print_(tree->right);
  440.             }
  441.         }
  442.         Pivo(){
  443.             root = nullptr;
  444.         }
  445.         static void print2(Node* &t){
  446.             std::cout << std::endl << t->x << ' ' << (t->left == nullptr) << ' ' << (t->right == nullptr) << std::endl;
  447.             std::cout << t->dop << ' ' << t->sum << ' ' << t->x << ' ' << size_(t) << std::endl;
  448.             if (t->left) std::cout << t->left->dop << ' ' << t->left->sum << ' ' << t->left->x << std::endl;
  449.             else std::cout << "No left" << std::endl;
  450.             if (t->right) std::cout << t->right->dop << ' ' << t->right->sum << ' ' << t->right->x << std::endl;
  451.             else std::cout << "No right" << std::endl;
  452.         }
  453.         static void add_reverse(Node* &tree, int start, int finish){
  454.             if (tree == nullptr){
  455.                 return;
  456.             }
  457.             std::pair<Node*, Node*> forest1 = split(tree, finish + 1);
  458.             std::pair<Node*, Node*> forest2 = split(forest1.first, start);
  459.             add_rev(forest2.second, 1);
  460.     // f(forest2.second, val);
  461.             Node* help_tree = merge_(forest2.first, forest2.second);
  462.             tree = merge_(help_tree, forest1.second);
  463.             push(tree);
  464.         }
  465. };
  466.  
  467. int main(){
  468.    /* int n;
  469.     std::cin >> n;
  470.     std::vector<int> s(n);
  471.     Pivo tree;
  472.     for (int i = 0; i < n; ++i) std::cin >> s[i];
  473.     tree.build(s);
  474.     tree.print();
  475.     std::cout << std::endl << tree.get(2, 4, "sum") << std::endl;
  476.     $$
  477.     tree.operation(5, 2, 4, "add");
  478.     tree.print();
  479.     std::cout << std::endl << tree.get(2, 4, "sum") << std::endl;
  480.     tree.print();
  481.     std::cout << "gavnoooooooooooo" << std::endl;
  482.     tree.operation(10, 1, 3, "assign");
  483.     $$
  484.     std::cout << tree.get(2, 4, "get") << "  huy\n";
  485.     $$
  486.     tree.print();
  487.     $$
  488.     tree.operation(1, 0, 2, "rev");
  489.     tree.operation(6, 1, 1, "assign");
  490.     tree.print();
  491.     tree.del(1);
  492.     $$
  493.     tree.print();
  494.     $$
  495.     tree.ins(17, 2);
  496.     tree.print();
  497.     $$
  498.     std::cout << tree.get(0, 4, "min") << ' ' << tree.get(0, 4, "max") << ' ' << tree.get(0,  4, "sum") << std::endl;
  499.     */
  500.     int type, n, m;
  501.     std::cin >> n;
  502.     std::vector<int> s(n);
  503.     for (int i = 0; i < n; ++i){
  504.         std::cin >> s[i];
  505.     }
  506.     Pivo tree;
  507.     //$$
  508.     tree.build(s);
  509.     //$$
  510.     //std::cout << n << ' ' << m << std::endl;
  511.     while (1){
  512.         int a, b;
  513.         std::cin >> a >> b;
  514.         tree.operation(1, a, b, "next");
  515.         tree.print();
  516.         std::cout << std::endl;
  517.     }
  518.     return 0;
  519. }
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. OK, I Understand
Top