Submission #424299

#	Time	Username	Problem	Language	Result	Execution time	Memory
424299		AugustinasJucas	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	541 ms	243176 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
struct node{
	char val;
	bool hasmin = 0;
	int left, right;
};

const int dydis = 10000000;
node tree[dydis];
const int dd = 1e6 + 1;
int dbIndd = 0, dbInd ;
vector<int> roots;
int curPlace = 0;
void build(int v){
	if(v >= dd){
		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].hasmin = 1;
		tree[v].left = v*2;
		tree[v].right = v*2+1;
	}
}
void Init() {
	build(1);
	dbInd = dd*2 + 2;
	roots.push_back(1);
}
int it = 0;
int mid;
void addLast(int v, int ka, int tl = 0, int tr = -2){
	if(tr == -2) tr = dd-1;
	mid = (tl + tr) / 2;
	//if(it++ > 20) exit(0);
	//cout << "v = " << v << ", ka = " << ka << ", mano int: [" <<tree[v].l << "; " << tree[v].r << "]\n";
	if(tl == tr){
		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, tl, mid);
	}else{
		tree[dbInd] = tree[tree[v].right];
		tree[v].right = dbInd;
		addLast(dbInd++, ka, mid+1, tr);
	}
	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, int tl = 0, int tr = -2){
	if(tr == -2) tr = dd-1;

	if(tr < x || x < tl) return 0;
	mid = (tl + tr) / 2;
//	cout << "esu " << tl << "; " << tr << ", mid = " << mid << ", kaimynai [" << tl << "; " << mid << "], [" << mid+1 << "; "  << tr << "]\n";

	if(tl == tr){
//		cout << "ret " << tl << endl << endl;
		return tree[v].val;
	
	}

	if(tl <= x && x <= tr){
		return getVal(tree[v].left, x, tl, mid) + getVal(tree[v].right, x, mid+1, tr);
	}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)));
}
/*
10
T a
T b
T c
T d
T e
T f
P 5
*/ 

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