#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;
~~^~~
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |