Submission #424262

#	Time	Username	Problem	Language	Result	Execution time	Memory
424262		AugustinasJucas	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	886 ms	262144 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
struct node{
	int l, r, val;
	int hasmin = 0;
	int left, right;
};
vector<node> tree;
const int dydis = 2000000 * 5;
const int dd = 1e6 + 1;
int dbIndd = 0, dbInd ;
vector<int> roots;
int curPlace = 0;
void build(int v){
	if(v >= dd){
		tree[v].l = tree[v].r = dbIndd++;
		tree[v].val = -1;
		tree[v].hasmin = 1;
		tree[v].left = tree[v].right = -1;
	}else{
		build(v*2); build(v*2+1);
		tree[v].l = tree[v*2].l;
		tree[v].r = tree[v*2+1].r;
		tree[v].hasmin = 1;
		tree[v].left = v*2;
		tree[v].right = v*2+1;
	}
}
void Init() {
	tree.resize(dydis);
	build(1);
	dbInd = dd*2 + 2;
	roots.push_back(1);
}
int it = 0;
void addLast(int v, int ka){
	//if(it++ > 20) exit(0);
	//cout << "v = " << v << ", ka = " << ka << ", mano int: [" <<tree[v].l << "; " << tree[v].r << "]\n";
	if(tree[v].l == tree[v].r){
		tree[v].val = ka;
		tree[v].hasmin = tree[v].val == -1;
		//cout << "padarau " << tree[v].l << " i " << ka << endl;
		//cout << "[" << tree[v].l << "; " << tree[v].r << "].hasmin = " << tree[v].hasmin << endl;
		return;
	}
	if(tree[tree[v].left].hasmin){ 
	//	cout << "eisim i kaire!" << ", ten siaip yra " << tree[v].left << ", tai as ji nukopijuoju i " << dbInd << endl;
		tree[dbInd] = tree[tree[v].left];
		tree[v].left = dbInd;
		addLast(dbInd++, ka);
	}else{
		tree[dbInd] = tree[tree[v].right];
		tree[v].right = dbInd;
		addLast(dbInd++, ka);
	}
	tree[v].hasmin = tree[tree[v].left].hasmin | tree[tree[v].right].hasmin;
	//cout << "[" << tree[v].l << "; " << tree[v].r << "].hasmin = " << tree[v].hasmin << endl;
}
int getVal(int v, int x){
	if(tree[v].r < x || x < tree[v].l) return 0;
	if(tree[v].l == tree[v].r) return tree[v].val;
	if(tree[v].l <= x && x <= tree[v].r){
		return getVal(tree[v].left, x) + getVal(tree[v].right, x);
	}else{
		return 0;
	}
}

void print(int v){
	if(tree[v].l == tree[v].r){
		if(tree[v].val == -1) return;
		cout << ((char)('a' + tree[v].val));
		return;
	}
	print(tree[v].left);
	print(tree[v].right);
}
	

void TypeLetter(char L) {
	//cout << "rasom " << L << " raide " << endl;
	tree[dbInd] = tree[roots.back()];
	//cout << "kol kas" << endl;
	int bv = dbInd;
	dbInd++;
	addLast(dbInd-1, L-'a');
	roots.push_back(bv);
	//cout << "po typinant: "; print(roots.back());
	//cout << endl;
}

void UndoCommands(int U) {
	tree[dbInd] = tree[roots[roots.size()-1-U]];
	roots.push_back(dbInd);
	//cout << "po udno: "; print(roots.back());
	//cout << endl;
	dbInd++;
}

char GetLetter(int P) {
	
	return ((char)('a' + getVal(roots.back(), P)));
}

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