oj.uz

Submission #169948

# Submission time Handle Problem Language Result Execution time Memory
169948 2019-12-23T11:02:43 Z CaroLinda Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 941 ms 183352 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 4 ms 888 KB Output is correct
3 Correct 4 ms 1272 KB Output is correct
4 Correct 5 ms 1268 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct
6 Correct 5 ms 1524 KB Output is correct
7 Correct 5 ms 1524 KB Output is correct
8 Correct 5 ms 1144 KB Output is correct
9 Correct 5 ms 1268 KB Output is correct
10 Correct 4 ms 888 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 150268 KB Output is correct
2 Correct 674 ms 165668 KB Output is correct
3 Correct 689 ms 162932 KB Output is correct
4 Correct 672 ms 140168 KB Output is correct
5 Correct 813 ms 141908 KB Output is correct
6 Correct 721 ms 179356 KB Output is correct
7 Correct 653 ms 87532 KB Output is correct
8 Correct 701 ms 139384 KB Output is correct
9 Correct 823 ms 183352 KB Output is correct
10 Correct 563 ms 139068 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 138656 KB Output is correct
2 Correct 924 ms 140404 KB Output is correct
3 Correct 700 ms 139848 KB Output is correct
4 Correct 637 ms 94328 KB Output is correct
5 Correct 657 ms 138840 KB Output is correct
6 Correct 642 ms 139452 KB Output is correct
7 Correct 686 ms 139048 KB Output is correct
8 Correct 822 ms 75320 KB Output is correct
9 Correct 941 ms 140924 KB Output is correct
10 Correct 559 ms 139064 KB Output is correct