oj.uz

Submission #118490

# Submission time Handle Problem Language Result Execution time Memory
118490 2019-06-19T05:46:24 Z win11905 Crayfish scrivener (IOI12_scrivener) C++11
34 / 100
 593 ms 262144 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 62968 KB Output is correct
2 Correct 91 ms 62968 KB Output is correct
3 Correct 95 ms 62984 KB Output is correct
4 Correct 93 ms 62968 KB Output is correct
5 Correct 91 ms 62944 KB Output is correct
6 Correct 92 ms 62968 KB Output is correct
7 Correct 93 ms 63016 KB Output is correct
8 Correct 101 ms 62952 KB Output is correct
9 Correct 91 ms 63000 KB Output is correct
10 Correct 92 ms 62968 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 62940 KB Output is correct
2 Correct 92 ms 62940 KB Output is correct
3 Correct 93 ms 62968 KB Output is correct
4 Correct 92 ms 63016 KB Output is correct
5 Correct 92 ms 62968 KB Output is correct
6 Correct 93 ms 62968 KB Output is correct
7 Correct 91 ms 63016 KB Output is correct
8 Correct 94 ms 63024 KB Output is correct
9 Correct 92 ms 62972 KB Output is correct
10 Correct 92 ms 62944 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 63876 KB Output is correct
2 Correct 95 ms 63992 KB Output is correct
3 Correct 95 ms 64120 KB Output is correct
4 Correct 152 ms 64888 KB Output is correct
5 Correct 92 ms 64084 KB Output is correct
6 Correct 94 ms 65416 KB Output is correct
7 Correct 95 ms 65372 KB Output is correct
8 Correct 94 ms 64760 KB Output is correct
9 Correct 96 ms 64888 KB Output is correct
10 Correct 93 ms 63992 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 456 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 593 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -