#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
struct node;
using node_ptr = node*;
struct node
{
int len;
char l;
node_ptr upread[21];
node_ptr upundo[21];
node()
{
l = '0';
len = 0;
for (int i = 0; i < 21; i++)
{
upread[i] = this;
upundo[i] = this;
}
}
node(char il, node_ptr lr, node_ptr lu) : l(il)
{
upread[0] = lr;
upundo[0] = lu;
len = lr->len + 1;
for (int i = 1; i < 21; i++)
{
upread[i] = (upread[i - 1] != 0 ? upread[i - 1]->upread[i - 1] : node_ptr());
upundo[i] = (upundo[i - 1] != 0 ? upundo[i - 1]->upundo[i - 1] : node_ptr());
}
}
node_ptr getundo(int k)
{
node_ptr cp = this;
for (int i = 20; i >= 0; i--)
{
if (k & (1ll<<i)) cp = cp->upundo[i];
assert(cp != 0);
}
return cp;
}
node_ptr getread(int k)
{
node_ptr cp = this;
for (int i = 20; i >= 0; i--)
{
if (k & (1ll<<i)) cp = cp->upread[i];
assert(cp != 0);
}
return cp;
}
};
node_ptr back;
void Init()
{
back = new node();
}
void TypeLetter(char L)
{
back = new node(L, back, back);
}
void UndoCommands(signed U)
{
node_ptr rep = back->getundo(U);
back = new node(rep->l, rep->upread[0], back);
}
char GetLetter(signed P)
{
int ind = back->len - 1 - P;
node_ptr rd = back->getread(ind);
return rd->l;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
896 KB |
Output is correct |
2 |
Correct |
7 ms |
1280 KB |
Output is correct |
3 |
Correct |
7 ms |
1792 KB |
Output is correct |
4 |
Correct |
7 ms |
1792 KB |
Output is correct |
5 |
Correct |
7 ms |
1536 KB |
Output is correct |
6 |
Correct |
7 ms |
1920 KB |
Output is correct |
7 |
Correct |
7 ms |
1792 KB |
Output is correct |
8 |
Correct |
7 ms |
1920 KB |
Output is correct |
9 |
Correct |
7 ms |
1792 KB |
Output is correct |
10 |
Correct |
7 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
883 ms |
247416 KB |
Output is correct |
2 |
Runtime error |
955 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1067 ms |
226236 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |