oj.uz

Submission #246614

# Submission time Handle Problem Language Result Execution time Memory
246614 2020-07-09T17:40:20 Z ant101 Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 750 ms 155640 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 4 ms 384 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 4 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 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 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 4 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 4 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 6 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 7 ms 1024 KB Output is correct
10 Correct 6 ms 640 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 127556 KB Output is correct
2 Correct 575 ms 140920 KB Output is correct
3 Correct 455 ms 138872 KB Output is correct
4 Correct 451 ms 112348 KB Output is correct
5 Correct 504 ms 121080 KB Output is correct
6 Correct 516 ms 152508 KB Output is correct
7 Correct 485 ms 76536 KB Output is correct
8 Correct 502 ms 113912 KB Output is correct
9 Correct 587 ms 155640 KB Output is correct
10 Correct 303 ms 114552 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 109744 KB Output is correct
2 Correct 750 ms 97452 KB Output is correct
3 Correct 435 ms 107256 KB Output is correct
4 Correct 431 ms 81528 KB Output is correct
5 Correct 455 ms 116600 KB Output is correct
6 Correct 447 ms 109944 KB Output is correct
7 Correct 484 ms 117240 KB Output is correct
8 Correct 572 ms 58104 KB Output is correct
9 Correct 677 ms 100600 KB Output is correct
10 Correct 308 ms 113528 KB Output is correct