Submission #9964181

Source Code Expand

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<ctime>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 1000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define P_TYPE int
typedef pair<P_TYPE, P_TYPE> P;
typedef pair<P, P_TYPE> PI;
typedef pair<P_TYPE, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

template<typename T>
class RedBlackTree {
  enum NODE_COLOR { BLACK, RED };
  struct Node {
    Node *left, *right, *prt;
    T key;
    int color;
    int size;

    Node(T x) {
      left = right = prt = nullptr;
      color = RED;
      key = x;
      size = 1;
    }

    inline bool is_left(Node *node) const {
      return this->left == node;
    }

    inline void assign(Node *node) {
      this->key = node->key;
    }

    inline Node* rotate_left() {
      Node *r = this->right, *m = r->left, *p = this->prt;
      if((r->prt = p)) {
        if(p->left == this) p->left = r;
        else p->right = r;
      }
      if((this->right = m)) m->prt = this;
      r->left = this; this->prt = r;

      int sz = this->size;
      this->size += (m ? m->size : 0) - r->size;
      r->size = sz;

      return r;
    }

    inline Node* rotate_right() {
      Node *l = this->left, *m = l->right, *p = this->prt;
      if((l->prt = p)) {
        if(p->left == this) p->left = l;
        else p->right = l;
      }
      if((this->left = m)) m->prt = this;
      l->right = this; this->prt = l;

      int sz = this->size;
      this->size += (m ? m->size : 0) - l->size;
      l->size = sz;

      return l;
    }

    inline Node* get_sib(Node *node) {
      return (this->is_left(node) ? this->right : this->left);
    }
  };

  Node *root;

  inline Node* find_node(Node *node, T x) {
    if(node == nullptr) return nullptr;
    while(node->key != x) {
      if(x < node->key) {
        if(!node->left) break;
        node = node->left;
      } else {
        if(!node->right) break;
        node = node->right;
      }
    }
    return node;
  }

  inline static bool is_red(Node *node) {
    return node && node->color == RED;
  }

  inline static bool is_black(Node *node) {
    return !node || node->color == BLACK;
  }

  inline void remove_node(Node *node) {
    Node *prt = node->prt;

    if(node->left && node->right) {
      Node *c_node = find_node(node->right, node->key);
      node->assign(c_node);
      node = c_node; prt = c_node->prt;
    }
    Node *dnode = node;

    Node *n_node = (node->left ? node->left : node->right);
    if(prt) {
      if(node->key < prt->key) {
        prt->left = n_node;
      } else {
        prt->right = n_node;
      }
    }
    if((node = n_node)) node->prt = prt;

    Node *cur = prt;
    while(cur) {
      --cur->size;
      cur = cur->prt;
    }

    if(is_red(dnode)) return;
    if(is_red(node)) {
      node->color = BLACK;
      if(!prt) this->root = node;
      return;
    }

    while(prt) {
      Node *sib = prt->get_sib(node);

      if(is_red(sib)) {
        if(prt->is_left(node)) {
          prt->rotate_left();
        } else {
          prt->rotate_right();
        }

        prt->color = RED;
        sib->color = BLACK;

        sib = prt->get_sib(node);
      }

      if(is_red(prt) || is_red(sib) || is_red(sib->left) || is_red(sib->right)) {
        if(is_red(prt) && is_black(sib) && is_black(sib->left) && is_black(sib->right)) {
          sib->color = RED;
          prt->color = BLACK;
          break;
        }

        if(is_black(sib)) {
          if(prt->is_left(node) && is_black(sib->right) && is_red(sib->left)) {
            Node *r = sib->rotate_right();
            r->color = RED;
            r->right->color = BLACK;
          } else if(!prt->is_left(node) && is_black(sib->left) && is_red(sib->right)) {
            Node *r = sib->rotate_left();
            r->color = RED;
            r->left->color = BLACK;
          }
          sib = prt->get_sib(node);
        }

        if(prt->is_left(node)) {
          prt->rotate_left();

          sib->color = prt->color;
          prt->color = sib->right->color = BLACK;
        } else {
          prt->rotate_right();

          sib->color = prt->color;
          prt->color = sib->left->color = BLACK;
        }
        break;
      }

      sib->color = RED;

      node = prt; prt = node->prt;
    }

    Node *n = (prt ? prt : node);
    if(n) {
      while(n->prt) n = n->prt;
    }
    this->root = n;
  }

public:
  RedBlackTree() {
    this->root = nullptr;
  }

  inline bool find(T x) {
    if(!this->root) return false;

    Node *node = find_node(this->root, x);
    return (node->key == x);
  }

  inline T at(int k) {
    if(!this->root) {
      return 0;
    }
    // assert(0 <= k < size);

    Node *node = this->root;
    ++k;
    while(1) {
      int l_size = (node->left ? node->left->size : 0) + 1;
      if(l_size == k) break;

      if(k < l_size) {
        node = node->left;
      } else {
        node = node->right;
        k -= l_size;
      }
    }
    return node->key;
  }

  inline bool insert(T x) {
    if(!this->root) {
      Node *new_node = new Node(x);
      this->root = new_node;
      new_node->color = BLACK;
      return true;
    }

    Node *node = find_node(this->root, x);
    if(node->key == x) return false;

    Node *new_node = new Node(x);
    if(x < node->key) {
      node->left = new_node;
    } else {
      node->right = new_node;
    }
    new_node->prt = node;

    while(node) {
      ++node->size;
      node = node->prt;
    }

    node = new_node;
    while(is_red(node->prt)) {
      Node *prt = node->prt;

      Node *gprt = prt->prt;
      Node *u = gprt->get_sib(prt);
      if(is_black(u)) {
        if(gprt->is_left(prt) && !prt->is_left(node)) {
          prt = prt->rotate_left();
          node = prt->left;
        } else if(!gprt->is_left(prt) && prt->is_left(node)) {
          prt = prt->rotate_right();
          node = prt->right;
        }

        if(prt->is_left(node)) {
          gprt->rotate_right();
        } else {
          gprt->rotate_left();
        }

        prt->color = BLACK;
        gprt->color = RED;

        break;
      }

      prt->color = u->color = BLACK;
      gprt->color = RED;

      node = gprt;
    }
    if(!node->prt) node->color = BLACK;

    while(node->prt) node = node->prt;
    this->root = node;

    return true;
  }

  inline bool remove(T x) {
    if(!this->root) {
      return false;
    }

    Node *node = find_node(this->root, x);
    if(node->key != x) {
      return false;
    }

    remove_node(node);
    return true;
  }

  int size() {
    return (this->root ? this->root->size : 0);
  }
};

int main() {
  RedBlackTree<int> tree;
  int q; scanf("%d", &q);
  while(q--) {
    int t, x; scanf("%d %d", &t, &x);
    switch(t) {
    case 1:
      tree.insert(x);
      break;
    case 2:
      x = tree.at(x-1);
      tree.remove(x);
      cout << x << "\n";
      break;
    }
  }
  return 0;
}

Submission Info

Submission Time
Task C - データ構造
User yaketake08
Language C++14 (GCC 5.4.1)
Score 100
Code Size 8312 Byte
Status AC
Exec Time 115 ms
Memory 9600 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:352:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int q; scanf("%d", &q);
                         ^
./Main.cpp:354:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int t, x; scanf("%d %d", &t, &x);
                                     ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 18
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KiB
sample_02.txt AC 1 ms 256 KiB
subtask1_01.txt AC 1 ms 256 KiB
subtask1_02.txt AC 1 ms 256 KiB
subtask1_03.txt AC 1 ms 256 KiB
subtask1_04.txt AC 5 ms 640 KiB
subtask1_05.txt AC 10 ms 1024 KiB
subtask1_06.txt AC 1 ms 256 KiB
subtask1_07.txt AC 62 ms 4736 KiB
subtask1_08.txt AC 66 ms 5632 KiB
subtask1_09.txt AC 63 ms 5504 KiB
subtask1_10.txt AC 109 ms 7552 KiB
subtask1_11.txt AC 111 ms 7552 KiB
subtask1_12.txt AC 105 ms 9600 KiB
subtask1_13.txt AC 115 ms 5504 KiB
subtask1_14.txt AC 115 ms 5504 KiB
subtask1_15.txt AC 84 ms 5504 KiB
subtask1_16.txt AC 81 ms 7552 KiB