Submission #169948

#	Time	Username	Problem	Language	Result	Execution time	Memory
169948		CaroLinda	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	941 ms	183352 KiB

scrivener

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i = a; i <b;i++)
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define sz size()
#define debug printf
#define ll long long
#define pii pair<int,int>

const int MAXN = 1e6+10;

using namespace std ;

struct Seg
{

	vector<int> e , d , soma ;

	int m(int l, int r) { return (l+r)>>1 ; }

	int create()
	{
		e.pb(0) ;
		d.pb(0) ;
		soma.pb(0) ;
		return (int)(e.sz) - 1 ;
	}

	int create_and_copy(int x)
	{
		e.pb(e[x]) ;
		d.pb(d[x]) ;
		soma.pb(soma[x]) ;
		return (int)(e.sz) - 1 ;
	}

	int upd(int pos,int l, int r, int idx)
	{
		int brandNew = create_and_copy(pos) ;

		if( l == r ) 
		{
			soma[brandNew] = 1 ;
			return brandNew ;
		}

		int aux ;

		if( idx <= m(l,r) )
		{
			aux = upd( e[brandNew] , l , m(l,r) , idx ) ;
			e[brandNew] = aux ;
		}
		else
		{
			aux = upd(d[brandNew] ,m(l,r)+1, r, idx ) ;
			d[brandNew] = aux ;
		}

		soma[brandNew] = soma[ e[brandNew] ] + soma[ d[brandNew] ] ;

		return brandNew ;

	}

	int binarySearch(int pos, int l, int r, int tot )
	{

		if(  l == r ) return l ;

		if( soma[e[pos]] >= tot ) return binarySearch(e[pos],l,m(l,r),tot) ;
		return binarySearch(d[pos],m(l,r)+1, r, tot - soma[e[pos]]) ;

	}

	void init()
	{
		e.clear() ;
		d.clear() ;
		soma.clear() ;
	}

} ;

int curId ;
int version[MAXN] ;
Seg seg ;
char letter[MAXN] ;

void Init() 
{

	seg.init() ;
	version[0] = 0 ;
	seg.create() ;
	curId = 0;

}

void TypeLetter(char L) {

	curId ++ ;

	version[curId] = seg.upd( version[curId-1] , 1 , MAXN , curId ) ;
	letter[curId] = L ;

}

void UndoCommands(int U) {

	curId ++ ;

	version[curId] = version[curId - U-1  ] ;

}

char GetLetter(int P) {

	return letter[ seg.binarySearch(version[curId],1,MAXN,P+1) ] ;

}

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