Submission #1239457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239457		guanex	Crayfish scrivener (IOI12_scrivener)	C++20	34 / 100	290 ms	327680 KiB

scrivener

#include<bits/stdc++.h>

using namespace std;

int sz[1000005];
int num = 0;

struct segtree{
  vector<vector<int>> t;
  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){
      t.push_back({lo, hi});
      let[cnt] = ' ';
      cnt++;
      return cnt-1;
    }
    int mid = lo + (hi - lo) / 2;
    int l = build(lo, mid);
    int r = build(mid+1, hi);
    t.push_back({l, r});
    let[cnt] = ' ';
    cnt++;
    return cnt-1;
  }
  int updt(int no, int lo, int hi, int tar, char l){
    if(lo == hi){
      let[cnt] = l;
      t.push_back({lo, hi});
      cnt++;
      return cnt-1; 
    } 
    int mid = lo + (hi - lo) / 2;
    if(tar <= mid){
      t.push_back((vector<int>){updt(t[no][0], lo, mid, tar, l), t[no][1]});
      let[cnt] = ' ';
      cnt++;
      return cnt-1;
    }else{
      t.push_back((vector<int>){t[no][0], updt(t[no][1], mid+1, hi, tar, l)});
      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(t[no][0], lo, mid, tar);
    }else{
      return query(t[no][1], 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: 0 / 26
• Subtask 5: 0 / 40