oj.uz

Submission #246373

# Submission time Handle Problem Language Result Execution time Memory
246373 2020-07-09T01:00:56 Z ant101 Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 704 ms 155768 KB 
#include <bits/stdc++.h>
#define N 1000050
#define log 22
using namespace std;
 
int n, id;
 
struct node
{
	char c;
 
	node *anc[log];
 
	int sz;
 
	node()
	{
		for(int i = 0; i < log ; i++) anc[i] = NULL;
 
		sz = 0;
	}
};
 
node *tree[N];
 
void TypeLetter(char c)
{
	int tmp = ++id;
 
	if(!tree[tmp]) tree[tmp] = new node();
 
	tree[tmp]->c = c;
 
	tree[tmp]->anc[0] = tree[tmp - 1];
 
	for(int i = 1; i < log; i++)
	{
	 	(tree[tmp]->anc[i]) = (tree[tmp]->anc[i - 1] ? (tree[tmp]->anc[i - 1])->anc[i - 1] : NULL);
	}
 
	tree[tmp]->sz = tree[tmp - 1]->sz + 1;
}
 
void UndoCommands(int k)
{
	int tmp = ++id;
 
	tree[tmp] = tree[tmp - k - 1];
}
 
char GetLetter(int k)
{	
	int tmp = id;
 
	node *root = tree[tmp];
 
	int up = root->sz - k - 1;
 
	for(int i = log - 1; i >= 0; i--)
	{
		if(up - (1<<i) >= 0)
		{
			up -= (1<<i);
 
			root = root->anc[i];
		}
	}
 
	return root->c;
}
 
void Init()
{
	id = 0;
 
	tree[0] = new node();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 4 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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 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 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 6 ms 1024 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 6 ms 1152 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 6 ms 768 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 124284 KB Output is correct
2 Correct 568 ms 140920 KB Output is correct
3 Correct 473 ms 138872 KB Output is correct
4 Correct 452 ms 112340 KB Output is correct
5 Correct 512 ms 120952 KB Output is correct
6 Correct 535 ms 152696 KB Output is correct
7 Correct 454 ms 76536 KB Output is correct
8 Correct 499 ms 113804 KB Output is correct
9 Correct 611 ms 155768 KB Output is correct
10 Correct 298 ms 114552 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 106104 KB Output is correct
2 Correct 696 ms 97376 KB Output is correct
3 Correct 481 ms 107384 KB Output is correct
4 Correct 441 ms 81440 KB Output is correct
5 Correct 467 ms 116728 KB Output is correct
6 Correct 463 ms 109940 KB Output is correct
7 Correct 470 ms 117120 KB Output is correct
8 Correct 601 ms 58104 KB Output is correct
9 Correct 704 ms 100728 KB Output is correct
10 Correct 293 ms 113528 KB Output is correct