Submission #350147

#	Time	Username	Problem	Language	Result	Execution time	Memory
350147		Kevin_Zhang_TW	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	505 ms	240348 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_M = 1000005 * 40, MAX_N = 1000005;

vector<int> res;
struct node {
	int cnt, left, right;
	char ret;
}room[MAX_M];
int newmem(int s) { 
	static int mem;
	return room[++mem] = room[s], mem;
}
int& C(int i) { return room[i].cnt; }
int& L(int i) { return room[i].left; }
int& R(int i) { return room[i].right; }
char& S(int i) { return room[i].ret; }

int insert(int root, char val) {
	int l = 0, r = MAX_N, m;
	int ret = newmem(root), now = ret;

	while (l < r) {
		m = l + r >> 1;
		int lsz = m - l + 1;
		// go right
		if (C(L(now)) == lsz) {
			now = R(now) = newmem(R(now));
			l = m + 1;
		}
		// go left
		else {
			now = L(now) = newmem(L(now));
			r = m;
		}
		++C(now);
	}
	S(now) = val;
	return ret;
}

char qry(int root, int k) {
	int l = 0, r = MAX_N, m;
	while (l < r) {
		m = l + r >> 1;
		if (k > m) {
			l = m + 1;
			root = R(root);
		}
		else {
			r = m;
			root = L(root);
		}
	}
	return S(root);
			

}

int curtime;

void Init() {
	res.pb(0);
}

void TypeLetter(char L) {

	res.pb(res.back());

	res.back() = insert(res.back(), L);

	++curtime;

}
void UndoCommands(int U) {

	res.pb(res[curtime - U]);

	++curtime;

}

char GetLetter(int P) {
	return qry(res.back(), P);
}

Compilation message (stderr)

scrivener.cpp: In function 'int insert(int, char)':
scrivener.cpp:39:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   m = l + r >> 1;
      |       ~~^~~
scrivener.cpp: In function 'char qry(int, int)':
scrivener.cpp:60:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   m = l + r >> 1;
      |       ~~^~~

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