Submission #237347

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
237347	2020-06-06T04:07:39 Z	T0p_	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	520 ms	207348 KB

scrivener

#include <bits/stdc++.h>
using namespace std;
 
struct node
{
	int l, r;
	char c;
};
 
int all, ver;
int root[1000005], heigh[1000005];
node seg[23000000];
 
int build(int l, int r)
{
	int now = ++all;
	if(l == r) return now;
	int mid = (l+r)>>1;
	int L = build(l, mid), R = build(mid+1, r);
	seg[now].l = L, seg[now].r = R;
	return now;
}
 
void Init() {
	root[0] = build(1, 1000000);
}
 
int update(int idx, int l, int r, int p, char c) {
	if(!(l <= p && p <= r)) return idx;
	int now = ++all;
	if(l == r)
	{
		seg[now].c = c;
		return now;
	}
	int mid = (l+r)>>1;
	int L = update(seg[idx].l, l, mid, p, c), R = update(seg[idx].r, mid+1, r, p, c);
	seg[now].l = L, seg[now].r = R;
	return now;
}
 
void TypeLetter(char L) {
	ver++;
	heigh[ver] = heigh[ver-1]+1;
	root[ver] = update(root[ver-1], 1, 1000000, heigh[ver], L);
}
 
void UndoCommands(int U) {
	ver++;
	heigh[ver] = heigh[ver-U-1];
	root[ver] = root[ver-U-1];
}
 
char query(int idx, int l, int r, int p)
{
	if(l == r) return seg[idx].c;
	int mid = (l+r)>>1;
	return (p <= mid) ? query(seg[idx].l, l, mid, p) : query(seg[idx].r, mid+1, r, p);
}
 
char GetLetter(int P) {
	return query(root[ver], 1, 1000000, P+1);
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	23808 KB	Output is correct
2	Correct	24 ms	23808 KB	Output is correct
3	Correct	39 ms	23800 KB	Output is correct
4	Correct	23 ms	23808 KB	Output is correct
5	Correct	23 ms	23808 KB	Output is correct
6	Correct	24 ms	23936 KB	Output is correct
7	Correct	23 ms	23800 KB	Output is correct
8	Correct	23 ms	23800 KB	Output is correct
9	Correct	24 ms	23808 KB	Output is correct
10	Correct	28 ms	23800 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	23808 KB	Output is correct
2	Correct	24 ms	23808 KB	Output is correct
3	Correct	24 ms	23800 KB	Output is correct
4	Correct	23 ms	23936 KB	Output is correct
5	Correct	24 ms	23824 KB	Output is correct
6	Correct	23 ms	23808 KB	Output is correct
7	Correct	24 ms	23808 KB	Output is correct
8	Correct	26 ms	23808 KB	Output is correct
9	Correct	24 ms	23808 KB	Output is correct
10	Correct	23 ms	23860 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	24192 KB	Output is correct
2	Correct	25 ms	24312 KB	Output is correct
3	Correct	26 ms	24312 KB	Output is correct
4	Correct	25 ms	24568 KB	Output is correct
5	Correct	30 ms	24312 KB	Output is correct
6	Correct	26 ms	24832 KB	Output is correct
7	Correct	25 ms	24824 KB	Output is correct
8	Correct	25 ms	24568 KB	Output is correct
9	Correct	25 ms	24576 KB	Output is correct
10	Correct	26 ms	24280 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	406 ms	174716 KB	Output is correct
2	Correct	410 ms	190204 KB	Output is correct
3	Correct	424 ms	186720 KB	Output is correct
4	Correct	435 ms	153208 KB	Output is correct
5	Correct	462 ms	165368 KB	Output is correct
6	Correct	422 ms	204024 KB	Output is correct
7	Correct	442 ms	110328 KB	Output is correct
8	Correct	421 ms	155768 KB	Output is correct
9	Correct	453 ms	207348 KB	Output is correct
10	Correct	361 ms	158712 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	462 ms	152184 KB	Output is correct
2	Correct	520 ms	136568 KB	Output is correct
3	Correct	425 ms	148088 KB	Output is correct
4	Correct	460 ms	115576 KB	Output is correct
5	Correct	402 ms	160252 KB	Output is correct
6	Correct	393 ms	152160 KB	Output is correct
7	Correct	410 ms	160720 KB	Output is correct
8	Correct	471 ms	87800 KB	Output is correct
9	Correct	520 ms	140024 KB	Output is correct
10	Correct	336 ms	157212 KB	Output is correct