Submission #621450

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
621450	2022-08-03T20:08:51 Z	SSRS	Collider (IZhO11_collider)	C++14	100 / 100	167 ms	49204 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(){
  }
  splay_tree(vector<T> A){
    root = dfs(A, 0, A.size());
  }
  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;
  }
  bool empty(){
    return root == nullptr;
  }
  int size(){
    return size(root);
  }
  int size(node* v){
    if (v == nullptr){
      return 0;
    }
    return v->sz;
  }
  void update(node* v){
    v->sz = 1 + size(v->ch[0]) + size(v->ch[1]);
  }
  int child_id(node *v){
    if (v->p == nullptr){
      return -1;
    } else if (v->p->ch[0] == v){
      return 0;
    } else {
      return 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(node* v, int c){
    node* w = v->ch[c ^ 1];
    update_child(v, w);
    v->ch[c ^ 1] = w->ch[c];
    if (w->ch[c] != nullptr){
      w->ch[c]->p = v;
    }
    v->p = w;
    w->ch[c] = v;
    update(v);
    update(w);
  }
  void splay(node* v){
    while (v->p != nullptr){
      node* p = v->p;
      node* g = p->p;
      int x = child_id(v);
      int y = child_id(p);
      if (y == -1){
        rotate(p, x ^ 1);
      } else if (x == y){
        rotate(g, x ^ 1);
        rotate(p, x ^ 1);
      } else {
        rotate(p, y);
        rotate(g, x);
      }
    }
    root = v;
  }
  node* get(int k){
    node* res = root;
    while (true){
      int s = size(res->ch[0]);
      if (k < s){
        res = res->ch[0];
      } else if (k == s){
        splay(res);
        return res;
      } else {
        k -= s + 1;
        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	14 ms	348 KB	Output is correct
3	Correct	20 ms	5176 KB	Output is correct
4	Correct	91 ms	39372 KB	Output is correct
5	Correct	130 ms	39356 KB	Output is correct
6	Correct	127 ms	44320 KB	Output is correct
7	Correct	133 ms	49192 KB	Output is correct
8	Correct	121 ms	49104 KB	Output is correct
9	Correct	167 ms	49204 KB	Output is correct
10	Correct	139 ms	49188 KB	Output is correct