Submission #406440

#	Time	Username	Problem	Language	Result	Execution time	Memory
406440		T0p_	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	561 ms	208892 KiB

scrivener

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

struct node
{
	char c;
	int L, R;
};

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

int build(int l, int r)
{
	int now = ++all;
	if(l == r) return now;
	int mid = (l+r)>>1;
	seg[now].L = build(l, mid), seg[now].R = build(mid+1, r);
	return now;
}

int update(int l, int r, int idx, 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(l, mid, seg[idx].L, p, c), R = update(mid+1, r, seg[idx].R, p, c);
	seg[now].L = L;
	seg[now].R = R;
	return now;
}

char query(int l, int r, int idx, int p)
{
	if(l == r) return seg[idx].c;
	int mid = (l+r)>>1;
	return (p <= mid) ? query(l, mid, seg[idx].L, p) : query(mid+1, r, seg[idx].R, p);
}

void Init()
{
	root[0] = build(1, 1000000);
}

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

void UndoCommands(int U)
{
	ver++;
	num[ver] = num[ver-U-1];
	root[ver] = root[ver-U-1];
}

char GetLetter(int P)
{
	return query(1, 1000000, root[ver], P+1);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40