Submission #1208682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208682		Dan4Life	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	259 ms	143644 KiB

scrivener

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

const int mxN = (int)1e6+2;
const int mxLg = 160;

template<int SZ>
struct PersistentSegTree{
	char seg[SZ*mxLg];
	int L[SZ*mxLg], R[SZ*mxLg];
	int IND;
	
	void init(){ IND = 1; L[IND]=R[IND]=0; }
	
	int newChild(char x){
		int ind = ++IND;
		L[ind]=R[ind]=0; seg[ind]=x;
		return ind;
	} 
	
	int newParent(int l, int r){
		int ind = ++IND;
		L[ind] = l, R[ind] = r;
		return ind;
	}
	
	int upd(int x, char v, int p, int l=1, int r=SZ){
		if(!p) return 0;
		if(l==r) return newChild(v);
		int mid = (l+r)/2;
		if(!L[p]) L[p] = ++IND;
		if(!R[p]) R[p] = ++IND;
		if(x<=mid) return newParent(upd(x,v,L[p],l,mid),R[p]);
		return newParent(L[p],upd(x,v,R[p],mid+1,r));
	}
	
	char query(int x, int p, int l=1, int r=SZ){
		if(l==r) return seg[p];
		int mid = (l+r)/2;
		if(x<=mid) return query(x,L[p],l,mid);
		return query(x,R[p],mid+1,r);
	}
};

PersistentSegTree<mxN> seg;

int rt[mxN], sz[mxN];
int cur;

void Init(){ seg.init(); rt[0] = 1; };

void TypeLetter(char L){
	sz[cur+1] = sz[cur]+1;
	rt[cur+1] = seg.upd(sz[cur]+1,L,rt[cur]);
	cur++;
};

void UndoCommands(int U){
	sz[cur+1] = sz[cur-U];
	rt[cur+1] = rt[cur-U];
	cur++;
};

char GetLetter(int P){ return seg.query(P+1,rt[cur]); };

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