Cod sursa(job #1720450)

Utilizator tudorcomanTudor Coman tudorcoman Data 22 iunie 2016 16:08:01
Problema Secv8 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.05 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
using namespace std;

class Node {
public:
  int val;
  int priority; // max heap
  int size;
  int sum;
  bool reversed;
  Node *lson;
  Node *rson;
};

Node *emptyNode = new Node{-1, -1, 0, 0, false, NULL, NULL};

inline void computeSize(Node *root) {
  if(root != emptyNode)
    root->size = 1 + root->lson->size + root->rson->size;
}

void propagate(Node* &root) {
  if(root == emptyNode)
    return ;
  if(root->reversed == true) {
    root->reversed = false;
    root->lson->reversed ^= 1;
    root->rson->reversed ^= 1;
    Node *aux = root->lson;
    root->lson = root->rson;
    root->rson = aux;
  }
}

void split(Node* root, int k, Node* &first, Node* &second) {
  propagate(root);
  if(root == emptyNode) {
    first = second = emptyNode;
  } else if(k <= root->lson->size) {
    split(root->lson, k, first, root->lson);
    second = root;
    computeSize(second);
  } else {
    split(root->rson, k - root->lson->size - 1, root->rson, second);
    first = root;
    computeSize(first);
  }
}

void Merge(Node* &root, Node* first, Node* second) {
  if(first == emptyNode) {
    root = second;
    return;
  } else if(second == emptyNode) {
    root = first;
    return;
  }

  propagate(first);
  propagate(second);
  if(first->priority < second->priority) {
    Merge(second->lson, first, second->lson);
    root = second;
  } else {
    Merge(first->rson, first->rson, second);
    root = first;
  }

  computeSize(root);
}

void Insert(Node* &root, int value, int priority, int k) {
  propagate(root);
  if(priority > root->priority) {
    Node *first = new Node{value, priority, 0, 0, NULL, NULL};
    split(root, k - 1, first->lson, first->rson);
    root = first;
    computeSize(root);
    return ;
  }

  if(k <= root->lson->size + 1)
    Insert(root->lson, value, priority, k);
  else
    Insert(root->rson, value, priority, k - root->lson->size - 1);

  computeSize(root);
}

int Erase(Node* &root, int k) {
  Node *first, *second, *third;
  split(root, k - 1, first, second);
  split(second, 1, second, third);
  Merge(root, first, third);
  int aux = second->val;
  delete second;
  return aux;
}

void EraseInterval(Node* &root, int st, int dr) {
  Node *first, *second, *third;
  split(root, st - 1, first, second);
  split(second, dr - st + 1, second, third);
  Merge(root, first, third);
  delete second;
}

void ReverseInterval(Node* &root, int st, int dr) {
  Node *first, *second, *third;
  split(root, st - 1, first, second);
  split(second, dr - st + 1, second, third);
  second->reversed = true;
  Merge(root, first, second);
  Merge(root, root, third);
}

int access(Node* &root, int k) {
  if(root == emptyNode)
    return -1;
  propagate(root);
  int posRoot = root->lson->size + 1;
  if(k < posRoot)
    return access(root->lson, k);
  else if(k == posRoot)
    return root->val;
  else
    return access(root->rson, k - posRoot);
}

void afis(Node *root) {
  if(root == emptyNode)
    return ;
  propagate(root);
  afis(root->lson);
  printf("%d ", root->val);
  afis(root->rson);
}

int main() {
  freopen("secv8.in", "r", stdin);
  freopen("secv8.out", "w", stdout);
  int N, nrnefolositor;
  scanf("%d %d\n", &N, &nrnefolositor);
  srand(time(0));
  Node *root = emptyNode;
  for(int i = 1; i <= N; ++ i) {
    char op;
    op = getc(stdin);
    switch(op) {
      case 'I': {
        int k, e; /// pos si val
        scanf(" %d %d\n", &k, &e);
        Insert(root, e, rand(), k);
        break;
      }
      case 'R': {
        int st, dr;
        scanf(" %d %d\n", &st, &dr);
        ReverseInterval(root, st, dr);
        break;
      }
      case 'A': {
        int pos;
        scanf(" %d\n", &pos);
        printf("%d\n", access(root, pos));
        break;
      }
      case 'D': {
        int st, dr;
        scanf(" %d %d\n", &st, &dr);
        EraseInterval(root, st, dr);
        break;
      }
    }
  }

  afis(root);
  return 0;
}