Submission #237284

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
237284	2020-06-05T17:27:06 Z	T0p_	Crayfish scrivener (IOI12_scrivener)	C++14	74 / 100	548 ms	262148 KB

scrivener

#include <bits/stdc++.h>
using namespace std;

struct node
{
	int v, l, r;
	char c;
};

int all, ver;
int root[1000005];
node seg[24000000];

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] = {0, L, 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].v = 1;
		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, seg[now].v = seg[L].v+seg[R].v;
	return now;
}

void TypeLetter(char L) {
	ver++;
	root[ver] = update(root[ver-1], 1, 1000000, seg[root[ver-1]].v+1, L);
}

void UndoCommands(int U) {
	ver++;
	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	28 ms	31616 KB	Output is correct
2	Correct	27 ms	31616 KB	Output is correct
3	Correct	27 ms	31744 KB	Output is correct
4	Correct	27 ms	31608 KB	Output is correct
5	Correct	27 ms	31616 KB	Output is correct
6	Correct	28 ms	31616 KB	Output is correct
7	Correct	28 ms	31740 KB	Output is correct
8	Correct	28 ms	31616 KB	Output is correct
9	Correct	28 ms	31616 KB	Output is correct
10	Correct	27 ms	31616 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	31616 KB	Output is correct
2	Correct	27 ms	31616 KB	Output is correct
3	Correct	28 ms	31608 KB	Output is correct
4	Correct	27 ms	31616 KB	Output is correct
5	Correct	30 ms	31744 KB	Output is correct
6	Correct	30 ms	31616 KB	Output is correct
7	Correct	27 ms	31608 KB	Output is correct
8	Correct	27 ms	31616 KB	Output is correct
9	Correct	29 ms	31616 KB	Output is correct
10	Correct	27 ms	31616 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	32128 KB	Output is correct
2	Correct	29 ms	32128 KB	Output is correct
3	Correct	29 ms	32256 KB	Output is correct
4	Correct	29 ms	32640 KB	Output is correct
5	Correct	30 ms	32256 KB	Output is correct
6	Correct	29 ms	32896 KB	Output is correct
7	Correct	29 ms	32768 KB	Output is correct
8	Correct	29 ms	32512 KB	Output is correct
9	Correct	29 ms	32640 KB	Output is correct
10	Correct	28 ms	32128 KB	Output is correct

Subtask #4

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	410 ms	224444 KB	Output is correct
2	Correct	423 ms	244088 KB	Output is correct
3	Correct	442 ms	239352 KB	Output is correct
4	Correct	457 ms	194424 KB	Output is correct
5	Correct	484 ms	211320 KB	Output is correct
6	Correct	453 ms	262140 KB	Output is correct
7	Correct	441 ms	137848 KB	Output is correct
8	Correct	441 ms	198264 KB	Output is correct
9	Runtime error	415 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Halted	0 ms	0 KB	-

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	475 ms	194960 KB	Output is correct
2	Correct	537 ms	174460 KB	Output is correct
3	Correct	450 ms	188920 KB	Output is correct
4	Correct	462 ms	146136 KB	Output is correct
5	Correct	420 ms	204360 KB	Output is correct
6	Correct	405 ms	193400 KB	Output is correct
7	Correct	447 ms	205048 KB	Output is correct
8	Correct	468 ms	108408 KB	Output is correct
9	Correct	548 ms	178084 KB	Output is correct
10	Correct	394 ms	199584 KB	Output is correct