Submission #44078

#	Time	Username	Problem	Language	Result	Execution time	Memory
44078		MrTEK	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1061 ms	262144 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e6 + 5;
#define mid (bas + son) / 2

int cnt,n = 1000000,c[N];

class tree{ public:
	int x;
	tree *l,*r;
};
typedef tree* pTree;

void build(pTree root,int bas,int son) {
	if (bas == son) {
		root -> x = 0;
		return;
	}
	root -> l = new tree;
	root -> r = new tree;
	build(root -> l,bas,mid);
	build(root -> r,mid + 1,son);
	root -> x = root -> l -> x + root ->r ->x;
}

pTree update(pTree root,int bas,int son,int wh,int val) {
	pTree t = new tree;
	if (bas == son && bas == wh) {
		t -> x = val;
		return t;
	}
	if (wh <= mid) {
		t -> l = update(root -> l,bas,mid,wh,val);
		t -> r = root -> r;
	}
	else {
		t -> l = root -> l;
		t -> r = update(root -> r,mid + 1,son,wh,val);
	}
	t -> x = t -> l -> x + t -> r -> x;
	return t;
}

int query(pTree root,int bas,int son,int wh) {
	if (bas > wh || son < wh) return 0;
	if (bas == wh && son == wh) return root -> x;
	return query(root -> l,bas,mid,wh) + query(root -> r,mid + 1,son,wh);
}

pTree T[N];

char last;

void Init() {
	T[0] = new tree;
	build(T[0],1,n);
}

void TypeLetter(char L) {
	T[cnt + 1] = update(T[cnt],1,n,c[cnt] + 1,(int) L);
	cnt++;
	c[cnt] = c[cnt - 1] + 1;
}

void UndoCommands(int U) {
	T[cnt + 1] = T[cnt - U];
	c[cnt + 1] = c[cnt - U];
	cnt++;
}

char GetLetter(int P) {
	return (char) query(T[cnt],1,n,P + 1);
}

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