SHARE
TWEET

without debug

a guest Feb 19th, 2020 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. #include <math.h>
  4. #include <map>
  5. #include <vector>
  6. #include <set>
  7. #include <deque>
  8. #include <algorithm>
  9. #include <list>
  10.  
  11. using namespace std;
  12.  
  13. #ifdef LOCAL
  14. #include <fstream>
  15. ifstream cin("tests.txt");
  16. ofstream cout("output1.txt");
  17. #else // LOCAL
  18. #include <iostream>
  19. #endif
  20.  
  21.  
  22.  
  23.  
  24.  
  25. #define ull unsigned long long
  26. #define ll long long
  27. #define pii pair<int,int>
  28.  
  29. #define DEBUG false
  30. #define CHECKER false
  31.  
  32. struct block {
  33.     deque<int> data;
  34.     bool rev;
  35.     int val;
  36.     block(int val = -1,bool rev = false) {
  37.         this->rev = rev;
  38.         this->val = val;
  39.     }
  40.  
  41.     int get_less(int x) {
  42.         if(this->val != -1)
  43.             if(this->val >= x)
  44.                 return data.size();
  45.             else
  46.                 return 0;
  47.  
  48.         int ans = this->data.size() - (lower_bound(this->data.begin(), this->data.end(), x) - this->data.begin());
  49.         return ans;
  50.     }
  51.  
  52.     void add_element(int x,bool to_l = false) {
  53.         to_l ^= this->rev;
  54.         if(to_l)
  55.             this->data.push_front(x);
  56.         else
  57.             this->data.push_back(x);
  58.     }
  59.  
  60.  
  61.     pair<block,block> split(int pos) {
  62.         //without the pos element
  63.         if(this->rev==true) {
  64.             pos = this->data.size()-pos-1;
  65.         }
  66.  
  67.         block lb;
  68.         for(int i = 0; i < pos; i++) {
  69.             lb.add_element(this->data[i]);
  70.         }
  71.         block rb;
  72.         for(int i = pos+1; i < this->data.size(); i++) {
  73.             rb.add_element(this->data[i]);
  74.         }
  75.  
  76.         if(this->rev) {
  77.             swap(lb,rb);
  78.             lb.rev = true;
  79.             rb.rev = true;
  80.         }
  81.  
  82.         lb.val = this->val;
  83.         rb.val = this->val;
  84.  
  85.         return {lb,rb};
  86.     }
  87.  
  88.     int get_el(int pos) {
  89.         if(this->rev==true) {
  90.             pos = this->data.size()-pos-1;
  91.         }
  92.         return this->data[pos];
  93.     }
  94. };
  95.  
  96. list<block> sqr;
  97.  
  98. void coutsqr();
  99.  
  100. void set_val(int l,int r,int x) {
  101.     int sl = 0;
  102.     int sr = -1;
  103.  
  104.  
  105.     for(auto i = sqr.begin(); i!= sqr.end(); i++) {
  106.         block & curblock = *i;
  107.         if(curblock.data.size()==0)
  108.             continue;
  109.         sl = sr+1;
  110.         sr = sl + curblock.data.size()-1;
  111.         if(sr<sl)
  112.             continue;
  113.  
  114.         if(sr < l)
  115.             continue;
  116.         if(sl > r)
  117.             continue;
  118.         if(l <= sl && sr <= r) {
  119.             curblock.val = x;
  120.             continue;
  121.         }
  122.         if(sl<=l && l<=sr && sl<=r && r<=sr) {
  123.             pair<block,block> blocks1 = curblock.split(l-sl);
  124.             block & lb1 = blocks1.first;
  125.             block & rb1 = blocks1.second;
  126.  
  127.             rb1.add_element(curblock.get_el(l-sl),true);
  128.  
  129.             sl = sl + lb1.data.size();
  130.  
  131.             pair<block,block> & blocks2 = rb1.split(r-sl);
  132.             block & lb2 = blocks2.first;
  133.             block & rb2 = blocks2.second;
  134.             lb2.add_element(rb1.get_el(r-sl));
  135.  
  136.             lb2.val = x;
  137.  
  138.             i = sqr.erase(i);
  139.             sqr.insert(i,lb1);
  140.             sqr.insert(i,lb2);
  141.             sqr.insert(i,rb2);
  142.             break;
  143.         }
  144.         if(sl<=l && l<=sr) {
  145.             pair<block,block> blocks = curblock.split(l-sl);
  146.             block & lb = blocks.first;
  147.             block & rb = blocks.second;
  148.             rb.add_element(curblock.get_el(l-sl),true);
  149.             rb.val = x;
  150.  
  151.             i = sqr.erase(i);
  152.             sqr.insert(i,lb);
  153.             sqr.insert(i,rb);
  154.             i--;
  155.             i--;
  156.             sr = sl + lb.data.size()-1;
  157.             continue;
  158.         }
  159.         if(sl<=r && r<=sr) {
  160.             pair<block,block> blocks = curblock.split(r-sl);
  161.             block & lb = blocks.first;
  162.             block & rb = blocks.second;
  163.             lb.add_element(curblock.get_el(r-sl));
  164.             lb.val = x;
  165.             i = sqr.erase(i);
  166.             sqr.insert(i,lb);
  167.             sqr.insert(i,rb);
  168.             i--;
  169.             i--;
  170.             continue;
  171.         }
  172.     }
  173. }
  174.  
  175.  
  176. int get_val(int l,int r,int x) {
  177.     int sl = 0;
  178.     int sr = -1;
  179.     int ans = 0;
  180.     for(auto i = sqr.begin(); i!= sqr.end(); i++) {
  181.         block & curblock = *i;
  182.         if(curblock.data.size()==0)
  183.             continue;
  184.         sl = sr+1;
  185.         sr = sl + curblock.data.size()-1;
  186.         if(sr<sl)
  187.             continue;
  188.  
  189.         if(sr < l)
  190.             continue;
  191.         if(sl > r)
  192.             continue;
  193.         if(l <= sl && sr <= r) {
  194.             ans += curblock.get_less(x);
  195.             continue;
  196.         }
  197.         if(sl<=l && l<=sr && sl<=r && r<=sr) {
  198.             pair<block,block> blocks1 = curblock.split(l-sl);
  199.             block & lb1 = blocks1.first;
  200.             block & rb1 = blocks1.second;
  201.             rb1.add_element(curblock.get_el(l-sl),true);
  202.  
  203.             sl = sl + lb1.data.size();
  204.  
  205.             pair<block,block> blocks2 = rb1.split(r-sl);
  206.             block & lb2 = blocks2.first;
  207.             block & rb2 = blocks2.second;
  208.             lb2.add_element(rb1.get_el(r-sl));
  209.  
  210.             ans += lb2.get_less(x);
  211.             break;
  212.         }
  213.         if(sl<=l && l<=sr) {
  214.             pair<block,block> blocks = curblock.split(l-sl);
  215.             block & lb = blocks.first;
  216.             block & rb = blocks.second;
  217.             rb.add_element(curblock.get_el(l-sl),true);
  218.  
  219.             ans += rb.get_less(x);
  220.             continue;
  221.         }
  222.         if(sl<=r && r<=sr) {
  223.             pair<block,block> blocks = curblock.split(r-sl);
  224.             block & lb = blocks.first;
  225.             block & rb = blocks.second;
  226.             lb.add_element(curblock.get_el(r-sl));
  227.  
  228.             ans += lb.get_less(x);
  229.             continue;
  230.         }
  231.     }
  232.     return ans;
  233. }
  234. void rreverse(int l,int r) {
  235.     int sl = 0;
  236.     int sr = -1;
  237.  
  238.     vector <block *> vect;
  239.     auto first_it = sqr.end();
  240.     bool first_it_b = true;
  241.     auto last_it = sqr.end();
  242.  
  243.     for(auto i = sqr.begin(); i!= sqr.end(); i++) {
  244.         block & curblock = *i;
  245.         if(curblock.data.size()==0)
  246.             continue;
  247.         sl = sr+1;
  248.         sr = sl + curblock.data.size()-1;
  249.         if(sr<sl)
  250.             continue;
  251.  
  252.         if(sr < l)
  253.             continue;
  254.         if(sl > r)
  255.             continue;
  256.         if(sl<=l && l<=sr && sl<=r && r<=sr) {
  257.             pair<block,block> blocks1 = curblock.split(l-sl);
  258.             block & lb1 = blocks1.first;
  259.             block & rb1 = blocks1.second;
  260.             rb1.add_element(curblock.get_el(l-sl),true);
  261.  
  262.             sl = sl + lb1.data.size();
  263.  
  264.             pair<block,block> blocks2 = rb1.split(r-sl);
  265.             block & lb2 = blocks2.first;
  266.             block & rb2 = blocks2.second;
  267.             lb2.add_element(rb1.get_el(r-sl));
  268.  
  269.             lb2.rev ^= 1;
  270.  
  271.             i = sqr.erase(i);
  272.             sqr.insert(i,lb1);
  273.             sqr.insert(i,lb2);
  274.             sqr.insert(i,rb2);
  275.  
  276.             break;
  277.         }
  278.         if(l <= sl && sr <= r) {
  279.             curblock.rev ^= 1;
  280.             if(first_it_b) {
  281.                 first_it_b = false;
  282.                 first_it = i;
  283.             }
  284.             last_it = i;
  285.             continue;
  286.         }
  287.         if(sl<=l && l<=sr) {
  288.             pair<block,block> blocks = curblock.split(l-sl);
  289.             block & lb = blocks.first;
  290.             block & rb = blocks.second;
  291.  
  292.  
  293.             rb.add_element(curblock.get_el(l-sl),true);
  294.  
  295.             i = sqr.erase(i);
  296.             sqr.insert(i,lb);
  297.             sqr.insert(i,rb);
  298.             i--;
  299.             i--;
  300.             sr = sl + lb.data.size()-1;
  301.             continue;
  302.         }
  303.         if(sl<=r && r<=sr) {
  304.             pair<block,block> blocks = curblock.split(r-sl);
  305.             block & lb = blocks.first;
  306.             block & rb = blocks.second;
  307.             lb.add_element(curblock.get_el(r-sl));
  308.  
  309.             i = sqr.erase(i);
  310.             lb.rev ^= 1;
  311.             sqr.insert(i,lb);
  312.             sqr.insert(i,rb);
  313.  
  314.             i--;
  315.             i--;
  316.             last_it = i;
  317.             continue;
  318.         }
  319.     }
  320. //    cout << "\n\n\n___AFTER_REVERSE\n";
  321. //            coutsqr();
  322. //            cout << "\n___AFTER_REVERSE\n\n\n";
  323.     reverse(first_it,++last_it);
  324. }
  325.  
  326.  
  327.  
  328. void build(vector<int> & a) {
  329.     int curr = 0;
  330.     int ss = sqrt(a.size());
  331.     for(int i = 0; i < ss; i++) {
  332.         block curblock;
  333.         for(int j = 0; j < ss; j++) {
  334.             curblock.add_element(a[curr++]);
  335.         }
  336.         sqr.push_back(curblock);
  337.     }
  338.     if(curr!=a.size()) {
  339.         block curblock;
  340.         while(curr != a.size()) {
  341.             curblock.add_element(a[curr++]);
  342.         }
  343.         sqr.push_back(curblock);
  344.     }
  345. }
  346.  
  347.  
  348. void coutsqr() {
  349.     for(auto i:sqr) {
  350.  
  351.         for(auto j:i.data) {
  352.             cout << j << ' ';
  353.         }
  354.         cout << " == " << i.val;
  355.         cout << " == " << i.rev;
  356.         cout << '\n';
  357.     }
  358.  
  359.  
  360. }
  361.  
  362. struct to_face {
  363.     vector<int> a;
  364.     to_face(vector<int> a) {
  365.         this->a = a;
  366.     }
  367.  
  368.     void sset(int l,int r, int x) {
  369.         for(int i = l; i <=r; i++) {
  370.             this->a[i] = x;
  371.         }
  372.     }
  373.     void rreverse(int l,int r) {
  374.         reverse(a.begin()+l,a.begin()+r+1);
  375.     }
  376.     int gget(int l, int r, int x) {
  377.         int ans = 0;
  378.         for(int i = l; i <=r; i++) {
  379.             if(this->a[i] >= x)
  380.                 ans++;
  381.         }
  382.         return ans;
  383.     }
  384. };
  385. to_face facer({0});
  386.  
  387. void rebuild() {
  388.     vector<int> a;
  389.     for(auto i:sqr) {
  390.         if(i.data.size()==0)
  391.             continue;
  392.         if(i.val != -1)
  393.             for(int t = 0; t < i.data.size(); t++)
  394.                 a.push_back(i.val);
  395.  
  396.         else {
  397.             if(i.rev)
  398.                 reverse(i.data.begin(),i.data.end());
  399.             for(auto j:i.data) {
  400.                 a.push_back(j);
  401.             }
  402.  
  403.         }
  404.     }
  405.     sqr.clear();
  406.     build(a);
  407. }
  408.  
  409.  
  410. bool checker() {
  411.     vector<int> a;
  412.     //cout << "CHECKER_WORKING:\n";
  413.     for(auto i:sqr) {
  414.         if(i.data.size()==0)
  415.             continue;
  416.         if(i.val != -1)
  417.             for(int t = 0; t < i.data.size(); t++) {
  418.                 a.push_back(i.val);
  419.             }
  420.  
  421.         else {
  422.             if(i.rev)
  423.                 for(int j = i.data.size()-1; j>=0; j--) {
  424.                     a.push_back(i.data[j]);
  425.                 } else
  426.                 for(auto j:i.data) {
  427.                     a.push_back(j);
  428.                 }
  429.  
  430.         }
  431.     }
  432.     for(int i = 0; i < a.size(); i++) {
  433.         if(a[i] != facer.a[i]) {
  434.             {
  435.                 cout << "\n\n__ERROR__\n\na:\n";
  436.                 for(auto &i:a)
  437.                     cout << i << ' ';
  438.                 cout << "\nFACER:\n";
  439.                 for(auto i:facer.a)
  440.                     cout << i << ' ';
  441.                 cout << "\nFASTER:\n";
  442.                 coutsqr();
  443.                 cout << "\n\n";
  444.                 exit(0);
  445.             }
  446.         }
  447.     }
  448. }
  449.  
  450.  
  451.  
  452. int main() {
  453. //#define int long long
  454.     int n;
  455.     cin >> n;
  456.     vector<int> a(n);
  457.     for(auto &i:a)
  458.         cin >> i;
  459. //    to_face facer({0});
  460.     if(CHECKER)
  461.         facer = to_face(a);
  462.     build(a);
  463.     int t;
  464.     cin >> t;
  465.     int sqqq = sqrt(t);
  466.     for(int i = 0; i < t; i++) {
  467.         string s="\n";
  468.  
  469.         cin >> s;
  470.         if(s=="get") {
  471.             int l,r,x;
  472.             cin >> l >> r >> x;
  473.             int fast_ans = get_val(--l,--r,x);
  474.             int fc_ans;
  475.             cout << fast_ans << '\n';
  476.         }
  477.         if(s=="set") {
  478.             int l,r,val;
  479.             cin >> l >> r >> val;
  480.             set_val(--l,--r,val);
  481.             if(CHECKER){
  482.                 facer.sset(l,r,val);
  483.                 checker();
  484.             }
  485.         }
  486.         if(s=="reverse") {
  487.             int l,r;
  488.             cin >> l >> r;
  489.             rreverse(--l,--r);
  490.             if(CHECKER){
  491.                 facer.rreverse(l,r);
  492.                 checker();
  493.             }
  494.         }
  495.         if(i%sqqq==0)
  496.             rebuild();
  497.     }
  498.     return 0;
  499. }
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