Advertisement
Guest User

Stiu ca sunt ff prost si ca nu e de mine da e frumos codu

a guest
Dec 5th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. mt19937 rnd((long long)(new char));
  6.  
  7. ifstream fin("secv8.in");
  8. ofstream fout("secv8.out");
  9.  
  10. typedef struct Treap * Arbore;
  11.  
  12. Arbore NIL;
  13.  
  14. void Join();
  15.  
  16. struct Treap {
  17.     bool flip;
  18.     int val;
  19.     int nl;
  20.     long long prio;
  21.     Arbore st;
  22.     Arbore dr;
  23.  
  24.     Treap(int val = 0) : flip(0), val(val), nl(1), prio(rnd()), st(NIL), dr(NIL) { }
  25.  
  26.     void propaga() {
  27.         if (!flip)
  28.             return;
  29.         swap(st, dr);
  30.         st->flip ^= 1;
  31.         dr->flip ^= 1;
  32.     }
  33.  
  34.     void recalc() {
  35.         nl = st->nl + dr->nl;
  36.     }
  37.  
  38.     void reverse_() {///nush daca o sa o folosesec dar sa fie acolo
  39.         flip ^= 1;
  40.     }
  41.  
  42.     void Split(Arbore &first, int cati, Arbore &second) {
  43.         if (this == NIL) {
  44.             assert(cati == 0);
  45.             first = NIL;
  46.             second = NIL;
  47.             return;
  48.         }
  49.         propaga();
  50.         if (cati > st->nl) {
  51.             first = this;
  52.             dr->Split(first->dr, cati - st->nl - 1, second);
  53.             first->recalc();
  54.         }
  55.         else {
  56.             second = this;
  57.             st->Split(first, cati, second->st);
  58.             second->recalc();
  59.         }
  60.     }
  61.  
  62.     void Insert(int poz, int val) {
  63.         Arbore first, second, Elm = new Treap(val), aux;
  64.         Split(first, poz - 1, second);
  65.         Join(first, Elm, aux);
  66.         Join(aux, second, this);
  67.     }
  68.  
  69.     int Access(int poz) {
  70.         assert(poz <= nl);
  71.         propaga();
  72.         Arbore first, _second, elm, second;
  73.         Split(first, poz - 1, _second);
  74.         _second->Split(elm, 1, second);
  75.         int val(elm->val);
  76.         Join(elm, second, _second);
  77.         Join(first, _second, this);
  78.         return val;
  79.     }
  80.  
  81.     void Reverse(int l, int r) {
  82.         Arbore left, middle, right, aux;
  83.         Split(left, l - 1, aux);
  84.         aux->Split(middle, r - l + 1, right);
  85.         middle->reverse_();
  86.         Join(middle, right, aux);
  87.         Join(left, aux, this);
  88.     }
  89.  
  90.     void Delete(int l, int r) {
  91.         Arbore left, middle, right, aux;
  92.         Split(left, l - 1, aux);
  93.         aux->Split(middle, r - l + 1, right);
  94.         Join(left, right, this);
  95.     }
  96.  
  97. };
  98.  
  99. int main()
  100. {
  101.     ///initializam NIL
  102.     NIL->flip = 0;
  103.     NIL->val = 0;
  104.     NIL->nl = 0;
  105.     NIL->prio = 0;
  106.     NIL->st = nullptr;
  107.     NIL->dr = nullptr;
  108.     Arbore v = NIL;
  109.     int q, a, b;
  110.     char ch;
  111.     bool uselesspentrucasuntpreaboss;
  112.     fin >> q >> uselesspentrucasuntpreaboss;
  113.     while (q--) {
  114.         fin >> ch;
  115.         if (ch == 'I') {
  116.             fin >> a >> b;
  117.             v->Insert(a, b);
  118.         }
  119.         else if (ch == 'A') {
  120.             fin >> a;
  121.             fout << v->Access(a) << '\n';
  122.         }
  123.         else if (ch == 'R') {
  124.             fin >> a >> b;
  125.             v->Reverse(a, b);
  126.         }
  127.         else {///if (ch == 'D)
  128.             fin >> a >> b;
  129.             v->Delete(a, b);
  130.         }
  131.     }
  132.     return 0;
  133. }
  134.  
  135. void Join(Arbore &first, Arbore &second, Arbore &ans) {
  136.     first->propaga();
  137.     second->propaga();
  138.     if (first == NIL) {
  139.         ans = second;
  140.         return;
  141.     }
  142.     if (second == NIL) {
  143.         ans = first;
  144.         return;
  145.     }
  146.     if (first->prio > second->prio) {
  147.         ans = first;
  148.         Join(first->dr, second, ans->dr);
  149.         ans->recalc();
  150.     }
  151.     else {
  152.         ans = second;
  153.         Join(first, second->st, ans->st);
  154.         ans->recalc();
  155.     }
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement