Cod sursa(job #2906871)

Utilizator andreic06Andrei Calota andreic06 Data 27 mai 2022 17:16:10
Problema Zeap Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.16 kb
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int INF = 2e9;
const int ERR = -1;

struct Treap {
   LL priority; int value;
   int maxx, miny;
   int min_dif;
   int size_of;

   Treap* left;
   Treap* right;
};
const Treap emptyTreap = { 0, 0, -INF, INF, INF, 0, NULL, NULL };

Treap* update_root ( Treap* root, Treap* new_left, Treap* new_right ) {

   int maxx = -INF;
   int miny = INF;
   int size_of = 1;
   int min_dif = INF;


   if ( new_left != NULL ) {
     maxx = max ( maxx, new_left -> maxx );
     miny = min ( miny, new_left -> miny );
     size_of += new_left -> size_of;

     min_dif = min ( min_dif, root -> value - new_left -> maxx );
     min_dif = min ( min_dif, new_left -> min_dif );
   }
   if ( new_right != NULL ) {
     maxx = max ( maxx, new_right -> maxx );
     miny = min ( miny, new_right -> miny );
     size_of += new_right -> size_of;

     min_dif = min ( min_dif, new_right -> miny - root -> value );
     min_dif = min ( min_dif, new_right -> min_dif );
   }
   root -> maxx = max ( maxx, root -> value );
   root -> miny = min ( miny, root -> value );
   root -> size_of = size_of;
   root -> min_dif = min_dif;
   root -> left = new_left; root -> right = new_right;
   return root;
}

pair<Treap*, Treap*> split ( Treap* root, int target ) {
   if ( root == NULL )
     return { NULL, NULL };
   if ( root -> value < target ) {
     auto p = split ( root -> right, target );
     root = update_root ( root, root -> left, p.first );
     return { root, p.second };
   }
   else { /// root -> value > target
     auto p = split ( root -> left, target );
     root = update_root ( root, p.second, root -> right );
     return { p.first, root };
   }
}
Treap* insert_in ( Treap* root, Treap* new_elem ) {
   if ( root == NULL )
     return new_elem;
   if ( root -> priority < new_elem -> priority ) {
     auto p = split ( root, new_elem -> value );
     new_elem = update_root ( new_elem, p.first, p.second );
     return new_elem;
   }
   /// altfel new_elem este in interior
   if ( root -> value < new_elem -> value ) {
     root -> right = insert_in ( root -> right, new_elem );
     root = update_root ( root, root -> left, root -> right );
     return root;
   }
   else {
     root -> left = insert_in ( root -> left, new_elem );
     root = update_root ( root, root -> left, root -> right );
     return root;
   }
}
Treap* finish_insert ( Treap* root, int x ) {
     Treap* aux = new Treap;
     LL new_priority = ( (long long) rand () << 31 ) ^ rand ();

     aux -> value = x;
     aux -> priority = new_priority;
     aux -> maxx = x; aux -> miny = x;
     aux -> size_of = 1; aux -> min_dif = INF;
     aux -> left = NULL; aux -> right = NULL;
     ///cout << new_priority << "\n";

     return insert_in ( root, aux );
}

bool find_elem ( Treap* root, int target ) {
   if ( root == NULL )
     return false;
   if ( root -> value == target )
     return true;

   if ( root -> value < target )
     return find_elem ( root -> right, target );
   else
     return find_elem ( root -> left, target );
}

Treap* join ( Treap* first, Treap* second ) {
   if ( first == NULL )
     return second;
   if ( second == NULL )
     return first;
   if ( first -> priority > second -> priority ) {
     first -> right = join ( first -> right, second );
     first = update_root ( first, first -> left, first -> right );
     return first;
   }
   else {
     second -> left = join ( first, second -> left );
     second = update_root ( second, second -> left, second -> right );
     return second;
   }
}
Treap* erase_out ( Treap* root, int target ) {
   if ( root == NULL )
     return NULL;
   if ( root -> value == target ) {
     root = join ( root -> left, root -> right );
     return root;
   }
   if ( root -> value < target ) {
     root -> right = erase_out ( root -> right, target );
     root = update_root ( root, root -> left, root -> right );
     return root;
   }
   else {
     root -> left = erase_out ( root -> left, target );
     root = update_root ( root, root -> left, root -> right );
     return root;
   }
}
int main()
{
   ifstream in ( "zeap.in" );
   ofstream out ( "zeap.out" );

   Treap* root = NULL;

   string query;
   while ( in >> query ) {
      if ( query == "I" ) {
        int x; in >> x;
        if ( find_elem ( root, x ) == false )
          root = finish_insert ( root, x );
      }
      else if ( query == "S" ) {
        int x; in >> x;
        if ( find_elem ( root, x ) == true )
          root = erase_out ( root, x );
        else
          out << ERR << "\n";
      }
      else if ( query == "C" ) {
        int x; in >> x;
        out << find_elem ( root, x ) << "\n";
      }
      else if ( query == "MAX" ) {
        if ( root != NULL && root -> size_of >= 2 )
          out << root -> maxx - root -> miny << "\n";
        else
          out << ERR << "\n";
      }
      else if ( query == "MIN" ) {
        if ( root != NULL && root -> size_of >= 2 )
          out << root -> min_dif << "\n";
        else
          out << ERR << "\n";
      }
   }
    return 0;
}