Submission #911637

#	Time	Username	Problem	Language	Result	Execution time	Memory
911637		Faisal_Saqib	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	221 ms	262144 KiB

scrivener

#include <iostream>
using namespace std;
struct StringTree
{
	char c='1';
	int s,e;
	int len=0;
	StringTree* next[2];
	StringTree(int l,int r,bool p=0)
	{
		s=l;
		e=r;
		if(s!=e and !p)
		{
			int mid=(s+e)/2;
			next[0]=new StringTree(s,mid);
			next[1]=new StringTree(mid+1,e);
		}
	}
	char  get(int&x)
	{
		if(s==e)
			return c;
		int mid=(s+e)/2;
		return next[(x>mid)]->get(x);
	}
};
const int MAXT=2e6+1;
StringTree* st[MAXT];
int tm=1;
StringTree* Update(StringTree* prev,char&c,int&ind)
{
	StringTree* tp=new StringTree(prev->s,prev->e,1);
	tp->len=prev->len+1;
	tp->c=c;
	if(prev->s==prev->e)
		return tp;
	int mid=(prev->s+prev->e)/2;
	if(ind<=mid)
	{
		tp->next[1]=prev->next[1];
		tp->next[0]=Update(prev->next[0],c,ind);
	}
	else
	{
		tp->next[0]=prev->next[0];
		tp->next[1]=Update(prev->next[1],c,ind);
	}
	return tp;
}
void Init()
{
	st[0]=new StringTree(0,MAXT);
}
void TypeLetter(char L)
{
	st[tm]=Update(st[tm-1],L,st[tm-1]->len);
	tm++;
}
void UndoCommands(int U)
{
	st[tm]=st[tm-U-1];
	tm++;
}
char GetLetter(int P)
{
	return st[tm-1]->get(P);
}

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