Submission #1208679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208679		Dan4Life	Crayfish scrivener (IOI12_scrivener)	C++17	0 / 100	252 ms	117560 KiB

scrivener

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
//#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using vi = vector<int>;
template <class T=int> using ar2 = array<T,2>;
template <class T=int> using ar3 = array<T,3>;

const int mxN = (int)1e6+2;
const int INF = (int)2e9;
const ll LINF = (ll)2e18;
const int MOD = (int)1e9+7;
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,rt[cur]); };

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