Submission #382350

#	Time	Username	Problem	Language	Result	Execution time	Memory
382350		alireza_kaviani	Crayfish scrivener (IOI12_scrivener)	C++11	100 / 100	757 ms	198012 KiB

scrivener

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

const int MAXN = 1e6 + 10;
const int LOG = 22;

int cur = 1 , nodeInd , root[MAXN] , seg[MAXN * LOG] , lc[MAXN * LOG] , rc[MAXN * LOG];
char ans[MAXN];

void build(int id = 0 , int l = 0 , int r = MAXN){
	if(r - l == 1)	return;
	int mid = l + r >> 1;
	lc[id] = ++nodeInd;
	rc[id] = ++nodeInd;
	build(lc[id] , l , mid);
	build(rc[id] , mid , r);
}

int modify(int x , int cid , int l = 0 , int r = MAXN){
	int id = ++nodeInd;
	seg[id] = seg[cid]; lc[id] = lc[cid]; rc[id] = rc[cid];
	if(r - l == 1){
		seg[id] = 1;
		return id;
	}
	int mid = l + r >> 1;
	if(x < mid)	lc[id] = modify(x , lc[id] , l , mid);
	else	rc[id] = modify(x , rc[id] , mid , r);
	seg[id] = seg[lc[id]] + seg[rc[id]];
	return id;
}

int get(int x , int id , int l = 0 , int r = MAXN){
	if(r - l == 1)	return l;
	int mid = l + r >> 1;
	if(seg[lc[id]] >= x)	return get(x , lc[id] , l , mid);
	return get(x - seg[lc[id]] , rc[id] , mid , r);
}

void Init() {
	build();
	return;
}

void TypeLetter(char L) {
	ans[cur] = L;
	root[cur] = modify(cur , root[cur - 1]);
//	cout << cur << ' ' << root[cur] << ' ' << seg[root[cur]] << endl;
	cur++;
}

void UndoCommands(int U) {
	root[cur] = root[cur - U - 1];
//	cout << cur << ' ' << root[cur] << endl;
	cur++;
}

char GetLetter(int P) {
	int res = get(P + 1 , root[cur - 1]);
//	cout << cur << ' ' << P << ' ' << res << endl;
	return ans[res];
}

Compilation message (stderr)

scrivener.cpp: In function 'void build(int, int, int)':
scrivener.cpp:12:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |  int mid = l + r >> 1;
      |            ~~^~~
scrivener.cpp: In function 'int modify(int, int, int, int)':
scrivener.cpp:26:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |  int mid = l + r >> 1;
      |            ~~^~~
scrivener.cpp: In function 'int get(int, int, int, int)':
scrivener.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int mid = l + r >> 1;
      |            ~~^~~

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