Submission #121666

#	Time	Username	Problem	Language	Result	Execution time	Memory
121666		Lawliet	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	430 ms	72896 KiB

scrivener

#include <bits/stdc++.h>
 
#define LOG 22
#define MAX 1000010
 
using namespace std;
 
class PersistentStack
{
	public:
		
		void add(char s)
		{
			curNode++;
			curVersion++;
			
			curTop = curNode;
			
			v[curNode] = s;
			version[curVersion] = curNode;
			dp[0][curNode] = version[curVersion - 1];
			prof[curNode] = prof[ dp[0][curNode] ] + 1;
						
			for(int k = 1 ; k < LOG ; k++)
			{
				int jump = dp[k - 1][curNode];
				dp[k][curNode] = dp[k - 1][jump];
			}
		}
		
		void back(int k)
		{
			curVersion++;
			
			version[curVersion] = version[curVersion - k - 1];
			
			curTop = version[ curVersion ];
		}
		
		char query(int k)
		{
			int d = prof[curTop] - k;
			int cur = curTop;
			
			for(int g = 0 ; g < LOG ; g++)
				if(d & (1 << g)) cur = dp[g][cur];
					
			return v[cur];
		}
		
	private:
		
		int curTop;
		int curNode;
		int curVersion;
		
		int prof[MAX];
		int dp[LOG][MAX];
		int version[MAX];
		
		char v[MAX];
};
 
PersistentStack p;
 
void Init() { }
 
void TypeLetter(char L) { p.add( L ); }
 
void UndoCommands(int U) { p.back( U ); }
 
char GetLetter(int P) { return p.query( P + 1 ); }

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