Submission #621441

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
621441	2022-08-03T19:53:34 Z	SSRS	Collider (IZhO11_collider)	C++14	100 / 100	141 ms	50296 KB

collider

#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct splay_tree{
  struct node{
    node* p;
    array<node*, 2> ch;
    int sz;
    T x;
    node(T x): p(nullptr), ch({nullptr, nullptr}), sz(1), x(x){
    }
  };
  node* root = nullptr;
  splay_tree(){
  }
  node* dfs(vector<T> &A, int L, int R){
    if (L == R){
      return nullptr;
    }
    int m = (L + R) / 2;
    node* v = new node(A[m]);
    node* l = dfs(A, L, m);
    v->ch[0] = l;
    if (l != nullptr){
      l->p = v;
    }
    node* r = dfs(A, m + 1, R);
    v->ch[1] = r;
    if (r != nullptr){
      r->p = v;
    }
    update(v);
    return v;
  }
  splay_tree(vector<T> A){
    root = dfs(A, 0, A.size());
  }
  int size(node* v){
    if (v == nullptr){
      return 0;
    }
    return v->sz;
  }
  int size(){
    return size(root);
  }
  void update(node* v){
    v->sz = 1 + size(v->ch[0]) + size(v->ch[1]);
  }
  void update_child(node* v, node *w){
    w->p = v->p;
    if (v->p == nullptr){
      return;
    }
     if (v->p->ch[0] == v){
      v->p->ch[0] = w;
    } else {
      v->p->ch[1] = w;
    }
  }
  void rotate_left(node* v){
    node* w = v->ch[1];
    update_child(v, w);
    v->ch[1] = w->ch[0];
    if (w->ch[0] != nullptr){
      w->ch[0]->p = v;
    }
    v->p = w;
    w->ch[0] = v;
    update(v);
    update(w);
  }
  void rotate_right(node* v){
    node* w = v->ch[0];
    update_child(v, w);
    v->ch[0] = w->ch[1];
    if (w->ch[1] != nullptr){
      w->ch[1]->p = v;
    }
    v->p = w;
    w->ch[1] = v;
    update(v);
    update(w);
  }
  void splay(node* v){
    while (v->p != nullptr){
      node* p = v->p;
      if (p->p == nullptr){
        if (v == p->ch[0]){
          rotate_right(p);
        } else {
          rotate_left(p);
        }
      } else {
        node* g = p->p;
        if (v == p->ch[0]){
          if (p == g->ch[0]){
            rotate_right(g);
            rotate_right(p);
          } else {
            rotate_right(p);
            rotate_left(g);
          }
        } else {
          if (p == g->ch[0]){
            rotate_left(p);
            rotate_right(g);
          } else {
            rotate_left(g);
            rotate_left(p);
          }
        }
      }
    }
    root = v;
  }
  node* get(int k){
    node* res = root;
    while (true){
      if (res->ch[0] != nullptr){
        if (k < res->ch[0]->sz){
          res = res->ch[0];
          continue;
        }
        k -= res->ch[0]->sz;
      }
      if (k == 0){
        splay(res);
        return res;
      }
      k--;
      res = res->ch[1];
    }
  }
  T operator [](int k){
    return get(k)->x;
  }
  void insert(int k, T x){
    node* v = new node(x);
    if (k == size(root)){
      v->ch[0] = root;
      if (root != nullptr){
        root->p = v;
      }
      root = v;
      update(v);
    } else {
      node* u = get(k);
      v->ch[0] = u->ch[0];
      v->ch[1] = u;
      if (u->ch[0] != nullptr){
        u->ch[0]->p = v;
      }
      u->ch[0] = nullptr;
      u->p = v;
      update(u);
      update(v);
      root = v;
    }
  }
  void erase(node* v){
    node* l = v->ch[0];
    node* r = v->ch[1];
    delete v;
    if (l == nullptr && r == nullptr){
      root = nullptr;
    } else if (l == nullptr){
      root = r;
      r->p = nullptr;    
    } else if (r == nullptr){
      root = l;
      l->p = nullptr;
    } else {
      r->p = nullptr;
      root = r;
      r = get(0);
      r->ch[0] = l;
      l->p = r;
      update(r);
    }
  }
  void erase(int k){
    erase(get(k));
  }
};
int main(){
  int n, m;
  cin >> n >> m;
  vector<char> c(n);
  for (int i = 0; i < n; i++){
    cin >> c[i];
  }
  splay_tree<char> ST(c);
  for (int i = 0; i < m; i++){
    char t;
    cin >> t;
    if (t == 'a'){
      int x, y;
      cin >> x >> y;
      x--;
      y--;
      splay_tree<char>::node* v = ST.get(x);
      char ans = v->x;
      ST.erase(v);
      ST.insert(y, ans);
    }
    if (t == 'q'){
      int x;
      cin >> x;
      x--;
      cout << ST[x] << endl;
    }
  }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	15 ms	456 KB	Output is correct
3	Correct	20 ms	5248 KB	Output is correct
4	Correct	91 ms	40260 KB	Output is correct
5	Correct	104 ms	40268 KB	Output is correct
6	Correct	124 ms	45260 KB	Output is correct
7	Correct	131 ms	50292 KB	Output is correct
8	Correct	107 ms	50164 KB	Output is correct
9	Correct	141 ms	50296 KB	Output is correct
10	Correct	123 ms	50292 KB	Output is correct