Submission #288336

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
288336	2020-09-01T12:25:40 Z	b00n0rp	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	647 ms	159816 KB

scrivener

#include<bits/stdc++.h>
using namespace std;

int SZ = 0,commands = 0;

const int LIM = 40000005;
const int MAXN = 1000005;

char seg[LIM];
int lft[LIM];
int rgt[LIM];

int root[MAXN],len[MAXN];

int build(int l,int r){
	int ind = ++SZ;
	if(l == r){
		seg[ind] = '.';
		return ind;
	}
	int mid = (l+r)/2;
	lft[ind] = build(l,mid);
	rgt[ind] = build(mid+1,r);
	return ind;
}

int update(int prev,int l,int r,int pos,char val){
	int ind = ++SZ;
	lft[ind] = lft[prev];
	rgt[ind] = rgt[prev];
	if(l == r){
		seg[ind] = val;
		return ind;
	}
	int mid = (l+r)/2;
	if(pos <= mid) lft[ind] = update(lft[prev],l,mid,pos,val);
	else rgt[ind] = update(rgt[prev],mid+1,r,pos,val);
	return ind;
}

char query(int ind,int l,int r,int pos){
	if(l == r) return seg[ind];
	int mid = (l+r)/2;
	if(pos <= mid) return query(lft[ind],l,mid,pos);
	else return query(rgt[ind],mid+1,r,pos);
}

void Init(){
	root[0] = build(0,1e6-1);
	len[0] = 0;
}

void TypeLetter(char L){
	commands++;
	len[commands] = len[commands-1]+1;
	root[commands] = update(root[commands-1],0,1e6-1,len[commands-1],L);
}

void UndoCommands(int U) {
	commands++;
	root[commands] = root[commands-U-1];
	len[commands] = len[commands-U-1];
}

char GetLetter(int P) {
	return query(root[commands],0,1e6-1,P);

}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	18048 KB	Output is correct
2	Correct	22 ms	17920 KB	Output is correct
3	Correct	21 ms	17920 KB	Output is correct
4	Correct	22 ms	17920 KB	Output is correct
5	Correct	23 ms	17920 KB	Output is correct
6	Correct	22 ms	17920 KB	Output is correct
7	Correct	22 ms	17912 KB	Output is correct
8	Correct	22 ms	18048 KB	Output is correct
9	Correct	22 ms	17912 KB	Output is correct
10	Correct	21 ms	17912 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	17912 KB	Output is correct
2	Correct	22 ms	17912 KB	Output is correct
3	Correct	22 ms	17920 KB	Output is correct
4	Correct	27 ms	17920 KB	Output is correct
5	Correct	21 ms	17920 KB	Output is correct
6	Correct	22 ms	17920 KB	Output is correct
7	Correct	22 ms	17920 KB	Output is correct
8	Correct	22 ms	17920 KB	Output is correct
9	Correct	21 ms	17920 KB	Output is correct
10	Correct	22 ms	17920 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	18304 KB	Output is correct
2	Correct	24 ms	18296 KB	Output is correct
3	Correct	23 ms	18412 KB	Output is correct
4	Correct	24 ms	18560 KB	Output is correct
5	Correct	24 ms	18304 KB	Output is correct
6	Correct	24 ms	18784 KB	Output is correct
7	Correct	24 ms	18680 KB	Output is correct
8	Correct	24 ms	18560 KB	Output is correct
9	Correct	26 ms	18508 KB	Output is correct
10	Correct	24 ms	18296 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	418 ms	130552 KB	Output is correct
2	Correct	431 ms	146424 KB	Output is correct
3	Correct	431 ms	144504 KB	Output is correct
4	Correct	469 ms	120952 KB	Output is correct
5	Correct	543 ms	128376 KB	Output is correct
6	Correct	451 ms	157076 KB	Output is correct
7	Correct	544 ms	88312 KB	Output is correct
8	Correct	469 ms	121956 KB	Output is correct
9	Correct	509 ms	159816 KB	Output is correct
10	Correct	340 ms	122848 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	504 ms	113640 KB	Output is correct
2	Correct	608 ms	107128 KB	Output is correct
3	Correct	442 ms	116088 KB	Output is correct
4	Correct	524 ms	92816 KB	Output is correct
5	Correct	409 ms	124536 KB	Output is correct
6	Correct	419 ms	118392 KB	Output is correct
7	Correct	425 ms	124920 KB	Output is correct
8	Correct	522 ms	71320 KB	Output is correct
9	Correct	647 ms	110028 KB	Output is correct
10	Correct	337 ms	121936 KB	Output is correct