Cod sursa(job #2421880)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 16 mai 2019 16:24:24
Problema Zeap Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.89 kb
#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
#define CHECKRET(x, y) if(!(x)) return (y);
#define SKIP(x) if((x)) continue;
typedef pair<int, int> pii;

#ifdef INFOARENA
#define ProblemName "zeap"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count());

struct node {
  int key, y, secondaryKey;
  node* left;
  node* right;
  int size;
  int minelem, maxelem, mindelta;
  node(int k, int sk) {
    key = k;
    secondaryKey = sk;
    left = right = 0;
    size = 1;
    y = rng();
    minelem = maxelem = k;
    mindelta = INT_MAX;
  }
};

inline bool isSmaller(int key, int sk, node *n) {
  if (key < n->key) return true;
  if (key > n->key) return false;
  return (sk < n->secondaryKey);
}

inline int size(node *p) {
  return p ? p->size : 0;
}

inline int minelem(node *p) {
  return p ? p->minelem : INT_MAX;
}

inline int maxelem(node *p) {
  return p ? p->maxelem : INT_MIN;
}

inline int mindelta(node *p) {
  return p ? p->mindelta : INT_MAX;
}

void recalc(node* p) {
  if (!p) return;
  p->size = size(p->left) + size(p->right) + 1;
  p->minelem = min(p->key, min(minelem(p->left), minelem(p->right)));
  p->maxelem = max(p->key, max(maxelem(p->left), maxelem(p->right)));
  p->mindelta = INT_MAX;
  if (p->left) {
    p->mindelta = min(p->mindelta, p->left->mindelta);
    p->mindelta = min(p->mindelta, p->key - p->left->maxelem);
  }
  if (p->right) {
    p->mindelta = min(p->mindelta, p->right->mindelta);
    p->mindelta = min(p->mindelta, p->right->minelem - p->key);
  }
}

void tsplit(node *root, int k, node **l, node **r, int sk) {
  if (root == NULL) {
    *l = NULL;
    *r = NULL;
    return;
  }
  if (isSmaller(k, sk, root)) {
    tsplit(root->left, k, l, &root->left, sk);
    *r = root;
    recalc(root);
  }
  else {
    tsplit(root->right, k, &root->right, r, sk);
    *l = root;
    recalc(root);
  }
}

node *tmerge(node *l, node *r) {
  if (l == NULL) return r;
  if (r == NULL) return l;
  if (l->y < r->y) {
    r->left = tmerge(l, r->left);
    recalc(r);
    return r;
  }
  else {
    l->right = tmerge(l->right, r);
    recalc(l);
    return l;
  }
}

node *tadd(node *root, node *n) {
  if (root == NULL) return n;
  if (n->y > root->y) {
    node *r, *l;
    tsplit(root, n->key, &l, &r, n->secondaryKey);
    n->left = l;
    n->right = r;
    recalc(n);
    return n;
  }
  if (isSmaller(n->key, n->secondaryKey, root))
    root->left = tadd(root->left, n);
  else
    root->right = tadd(root->right, n);
  recalc(root);
  return root;
}

node *tremove(node *root, int k) {

  if (root == NULL)
    return root;

  if (root->key == k) {
    node *bak = root;
    root = tmerge(root->left, root->right);
    delete bak;
    return root;
  }

  if (isSmaller(k, 0, root))
    root->left = tremove(root->left, k);
  else root->right = tremove(root->right, k);

  recalc(root);
  return root;
}

node *tkthelement(node *root, int k) {
  if (root == NULL)
    return NULL;
  if (size(root->left) == k - 1)
    return root;
  if (size(root->left) >= k)
    return tkthelement(root->left, k);
  return tkthelement(root->right, k - size(root->left) - 1);
}

inline void tIntervalSplit(node *root, int x, int y, node **l, node **mid, node **r) {
  node *splitNode = tkthelement(root, x);
  tsplit(root, splitNode->key, l, mid, splitNode->secondaryKey - 1);
  splitNode = tkthelement(*mid, y - size(*l));
  tsplit(*mid, splitNode->key, mid, r, splitNode->secondaryKey);
}

inline node *tIntervalMerge(node *l, node *mid, node *r) {
  node *root = tmerge(l, mid);
  return tmerge(root, r);
}

#define MPRINTPOS 100
#define MPRINTLVL 10
char printBuf[MPRINTLVL][MPRINTPOS];
char auxbuf[20];
void _tprint(node *root, int lvl = 0, int pleft = 0, int pright = MPRINTPOS) {
  if (root == NULL) return;
  int mid = (pleft + pright) / 2;
  sprintf(auxbuf, "%d (%d)", root->key, root->mindelta);
  memcpy(&printBuf[lvl][mid], auxbuf, strlen(auxbuf));
  _tprint(root->left, lvl + 1, pleft, mid);
  _tprint(root->right, lvl + 1, mid, pright);
}
void tprint(node *root) {
  for (int i = 0; i < MPRINTLVL; ++i)
    for (int j = 0; j < MPRINTPOS; ++j)
      printBuf[i][j] = ' ';
  _tprint(root, 0, 0, size(root) * 5);
  for (int i = 0; i < MPRINTLVL; ++i) {
    for (int j = 0; j < MPRINTPOS; ++j)
      putchar(printBuf[i][j]);
    putchar('\n');
  }
}

int texists(node **root, int k) {
  node *l, *r;
  tsplit(*root, k, &l, &r, INT_MAX);
  int rez = (size(l) > 0 && maxelem(l) == k) ? 1 : 0;
  *root = tmerge(l, r);
  return rez;
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  srand(41532);
  node *T = NULL;
  //int Q;
  //scanf("%d", &Q);
  int nseed = 0;
  for (;;) {
    char c;
    int x = 0, y = 0;
    node *l, *mid, *r;
    if (scanf(" %c", &c) != 1) break;
    int itmp; char tmp;
    switch (c) {
    case 'I':
      scanf("%d", &x);
      if (texists(&T, x) == 1)
        break;
      T = tadd(T, new node(x, nseed++));
      break;
    case 'S':
      scanf("%d", &x);
      itmp = size(T);
      T = tremove(T, x);
      if (size(T) == itmp) puts("-1");
      break;
    case 'C':
      scanf("%d", &x);
      printf("%d\n", texists(&T, x));
      break;
    case 'M':
      //scanf("%d%d", &x, &y);
      tmp = getchar(); getchar();
      x = 0, y = size(T) - 1;
      if (x >= y) {
        puts("-1");
        break;
      }
      ++x, ++y;
      tIntervalSplit(T, x, y, &l, &mid, &r);
      if (tmp == 'I')
        printf("%d\n", mid->mindelta);
      else printf("%d\n", mid->maxelem - mid->minelem);
      T = tIntervalMerge(l, mid, r);
      break;
    default:
      break;
    }
    //printf("---- %c %d %d ----\n", c, x, y);
    //puts("---- Trie is ----\n");
    //tprint(T);
  }
  return 0;
}