Cod sursa(job #1704461)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 18 mai 2016 20:36:36
Problema Secv8 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.83 kb
#include <fstream>
#include <algorithm>
#include <random>
#include <chrono>

using namespace std;

class Generator {
   private:
      mt19937_64 rGen;
   public:
      Generator() {
         int _time = chrono :: high_resolution_clock :: now().
                     time_since_epoch().count();
         rGen = mt19937_64(_time);
      }
      uint64_t Rand() {
         int64_t x = rGen();
         return (x < 0 ? -x : x);
      }
};

class Node {
   public:
      uint64_t p;
      int v;
      int size;
      bool rev;
      Node *left, *right;

      Node() {}
      Node(uint64_t _p, int _v, int _size, bool _rev, Node *_left, Node *_right) :
         p(_p), v(_v), size(_size), rev(_rev), left(_left), right(_right) {}
};

Generator randGen;
Node* NIL = new Node();
Node *root;

void Push(Node *t) {
   if(t->rev && t != NIL) {
      t->rev = 0;
      t->left->rev ^= 1;
      t->right->rev ^= 1;
      swap(t->left, t->right);
   }
}
    
Node *Write(Node *t, Node *l, Node *r) {
   t->size = l->size + 1 + r->size;
   t->left = l;
   t->right = r;
   return t;
}

pair<Node*, Node*> Split(Node *t, int i) {
   Push(t);
   
   if(t == NIL)
      return make_pair(NIL, NIL);
      
   Node *left, *right;
   pair<Node*, Node*> temp;
      
   if(t->left->size < i) {
      temp = Split(t->right, i - t->left->size - 1);
      left = Write(t, t->left, temp.first);
      right = temp.second;
   }
   else {
      temp = Split(t->left, i);
      left = temp.first;
      right = Write(t, temp.second, t->right);
   }
   
   return make_pair(left, right);
}

Node *Merge(Node *left, Node *right) {
   Push(left);
   Push(right);
   
   if(left == NIL)
      return right;
   if(right == NIL)
      return left;
   
   if(left->p <= right->p) 
      return Write(left, left->left, Merge(left->right, right));
   else 
      return Write(right, Merge(left, right->left), right->right);
}

int Find(Node *t, int p) {
   Push(t);
   
   if(t->left->size == p)
      return t->v;
   if(t->left->size > p)
      return Find(t->left, p);
   else
      return Find(t->right, p - t->left->size - 1);
}

Node *Insert(Node *t, int p, int v) {
   Node *_new = new Node(randGen.Rand(), v, 1, 0, NIL, NIL);
   pair<Node*, Node*> temp = Split(t, p);
   return Merge(Merge(temp.first, _new), temp.second);
}

Node *IntervalReverse(Node *t, int _begin, int _end) {
   pair<Node*, Node*> temp1, temp2;
   temp1 = Split(t, _begin);
   temp2 = Split(temp1.second, _end - _begin);
   temp2.first->rev ^= 1;
   return Merge(temp1.first, Merge(temp2.first, temp2.second));
}

void Delete(Node *t) {
   if(t->left != nullptr)
      Delete(t->left);
   if(t->right != nullptr);
      Delete(t->right);
   delete t;
}

Node *IntervalErase(Node *t, int _begin, int _end) {
   pair<Node*, Node*> temp1, temp2;
   temp1 = Split(t, _begin);
   temp2 = Split(temp1.second, _end - _begin);
   //Delete(temp2.first);
   return Merge(temp1.first, temp2.second);
}

int main() {
   ifstream f("secv8.in");
   ofstream g("secv8.out");
   
   int M, x, y;
   char crt;
   
   root = NIL = new Node();
   
   f >> M >> x;
   while(M--) {
      f >> crt;
      switch(crt) {
         case 'I':
            f >> x >> y;
            --x;
            root = Insert(root, x, y);
            break;
         case 'A':
            f >> x;
            --x;
            g << Find(root, x) << '\n';
            break;
         case 'R':
            f >> x >> y;
            --x;
            root = IntervalReverse(root, x, y);
            break;
         case 'D':
            f >> x >> y;
            --x;
            root = IntervalErase(root, x, y);
            break;
      }
   }
   
   for(int i = 0; i < root->size; i++)
      g << Find(root, i) << ' ';
   g << '\n';
   
   return 0;
}