Submission #118490

#	Time	Username	Problem	Language	Result	Execution time	Memory
118490		win11905	Crayfish scrivener (IOI12_scrivener)	C++11	34 / 100	593 ms	262144 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+1;

struct item {
  char val;
  item *l, *r;
  item(char val, item *l, item *r) : val(val), l(l), r(r) {}
};

item* newson(char val) { return new item(val, nullptr, nullptr); }
item* newpar(char val, item *l, item *r) { return new item(val, l, r); }

int step;
item* ver[N];
int sz[N];

item* build(int l = 0, int r = N) {
  if(l == r) return newson('0');
  int m = l + r >> 1;
  return newpar(0, build(l, m), build(m+1, r));  
}

char query(int pos, item* p, int l = 0, int r = N) {
  if(l == r) return p->val; 
  int m = l + r >> 1;
  if(pos <= m) return query(pos, p->l, l, m);
  else return query(pos, p->r, m+1, r);
}

item* update(int pos, char val, item *p, int l = 0, int r = N) {
  if(l == r) return newson(val);
  int m = l + r >> 1;
  if(pos <= m) return newpar(0, update(pos, val, p->l, l, m), p->r);
  else return newpar(0, p->l, update(pos, val, p->r, m+1, r));
}

void Init() {
  ver[0] = build();
}

void TypeLetter(char L) {
  ver[step+1] = update(sz[step+1] = sz[step], L, ver[step]);
  sz[++step]++;
}

void UndoCommands(int U) {
  ver[step+1] = ver[step-U];
  sz[step+1] = sz[step-U];
  step++;
}

char GetLetter(int P) {
  return query(P, ver[step]);
}

Compilation message (stderr)

scrivener.cpp: In function 'item* build(int, int)':
scrivener.cpp:21:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
scrivener.cpp: In function 'char query(int, item*, int, int)':
scrivener.cpp:27:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
scrivener.cpp: In function 'item* update(int, char, item*, int, int)':
scrivener.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~

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