Submission #1239461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239461		guanex	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	452 ms	223028 KiB

scrivener

#include<bits/stdc++.h>

using namespace std;

int sz[1000005];
int num = 0;

struct segtree{
  vector<int> left, right;
  char let[20000000];
  vector<int> roots;
  int cnt = 0;
  segtree(){
    int root = build(0, 1000001);
    roots.push_back(root);
  }
  int build(int lo, int hi){
    if(lo == hi){
      left.push_back(lo);
      right.push_back(hi);
      cnt++;
      return cnt-1;
    }
    int mid = lo + (hi - lo) / 2;
    int l = build(lo, mid);
    int r = build(mid+1, hi);
    left.push_back(l);
    right.push_back(r);
    cnt++;
    return cnt-1;
  }
  int updt(int no, int lo, int hi, int tar, char l){
    if(lo == hi){
      let[cnt] = l;
      left.push_back(lo);
      right.push_back(hi);
      cnt++;
      return cnt-1; 
    } 
    int mid = lo + (hi - lo) / 2;
    if(tar <= mid){
      int nl = updt(left[no], lo, mid, tar, l);
      left.push_back(nl);
      right.push_back(right[no]);
      cnt++;
      return cnt-1;
    }else{
      int nr = updt(right[no], mid+1, hi, tar, l);
      left.push_back(left[no]);
      right.push_back(nr);
      cnt++;
      return cnt-1;
    }
  }
  void update(int k, int pos, char l){
    roots[k] = updt(roots[k], 0, 1000001, pos, l);
  }
  char query(int no, int lo, int hi, int tar){
    if(lo == hi){
      return let[no];
    }
    int mid = lo + (hi - lo) / 2;
    if(tar <= mid){
      return query(left[no], lo, mid, tar);
    }else{
      return query(right[no], mid+1, hi, tar);
    }
  }
  char ask(int k, int pos){
    return query(roots[k], 0, 1000001, pos);
  }
  void copy(int k){
    roots.push_back(roots[k]);
  }
};

segtree tree;

void Init() {
  sz[0] = 0;
  num = 1;
}

void TypeLetter(char L) {
  tree.copy(num-1);
  tree.update(num, sz[num-1], L);
  sz[num] = sz[num-1]+1;
  num++;
}

void UndoCommands(int U) {
  int tar = num - U - 1;
  sz[num] = sz[tar];
  tree.copy(tar);
  num++;
}

char GetLetter(int P) {
  //cout << "answer " << tree.ask(num-1, P) << endl;
  return tree.ask(num-1, P);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40