Submission #44078

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44078	2018-03-29T19:25:04 Z	MrTEK	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1000 ms	262144 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	62996 KB	Output is correct
2	Correct	106 ms	63088 KB	Output is correct
3	Correct	109 ms	63172 KB	Output is correct
4	Correct	118 ms	63332 KB	Output is correct
5	Correct	133 ms	63332 KB	Output is correct
6	Correct	102 ms	63332 KB	Output is correct
7	Correct	109 ms	63332 KB	Output is correct
8	Correct	103 ms	63372 KB	Output is correct
9	Correct	101 ms	63372 KB	Output is correct
10	Correct	131 ms	63372 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	63428 KB	Output is correct
2	Correct	105 ms	63500 KB	Output is correct
3	Correct	108 ms	63560 KB	Output is correct
4	Correct	103 ms	63560 KB	Output is correct
5	Correct	110 ms	63580 KB	Output is correct
6	Correct	105 ms	63580 KB	Output is correct
7	Correct	103 ms	63708 KB	Output is correct
8	Correct	104 ms	63708 KB	Output is correct
9	Correct	101 ms	63708 KB	Output is correct
10	Correct	101 ms	63708 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	109 ms	64436 KB	Output is correct
2	Correct	112 ms	64592 KB	Output is correct
3	Correct	120 ms	64832 KB	Output is correct
4	Correct	117 ms	65688 KB	Output is correct
5	Correct	107 ms	65688 KB	Output is correct
6	Correct	106 ms	66136 KB	Output is correct
7	Correct	110 ms	66160 KB	Output is correct
8	Correct	108 ms	66160 KB	Output is correct
9	Correct	136 ms	66160 KB	Output is correct
10	Correct	103 ms	66160 KB	Output is correct

Subtask #4

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1061 ms	262144 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1033 ms	262144 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-