Submission #398648

#	Time	Username	Problem	Language	Result	Execution time	Memory
398648		hoaphat1	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	493 ms	262148 KiB

scrivener

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

const int N = 1e6 + 3;
struct node {
	node* L;
	node* R;
	char c;
	int cnt = 0;
	void apply(node* x) {
		L = x->L;
		R = x->R;
		c = x->c;
		cnt = x->cnt;
	}
};
node* s[N];
int n = 0;

struct segtree {
	void build(node*& R, int l, int r) {
		R = new node{};
		if (l == r) {
			return ;
		}
		int mid = l + r >> 1;
		build(R->L, l, mid);
		build(R->R, mid + 1, r);
	}
	node* modify(node* R, int l, int r, int pos, char c) {
		node* res = new node{};
 		if (l == r) {
			res->c = c;
			res->cnt = 1;
			return res;
		}
		res->L = R->L;
		res->R = R->R;
		int mid = l + r >> 1;
		if (pos <= mid) res->L = modify(R->L, l, mid, pos, c);
		else res->R = modify(R->R, mid + 1, r, pos, c);
		res->cnt = res->L->cnt + res->R->cnt;
		return res;
	}
	char get(node* R, int l, int r, int pos) {
		if (l == r) return R->c;
		int mid = l + r >> 1;
		if (pos <= mid) return get(R->L, l, mid, pos);
		return get(R->R, mid + 1, r, pos);
	}
};
segtree Tree;
string st[N];

void Init() {
	s[0] = new node{};
	Tree.build(s[0], 0, N - 1);
}

void TypeLetter(char L) {
	++n;
	s[n] = Tree.modify(s[n - 1], 0, N - 1, s[n - 1]->cnt, L);
}

void UndoCommands(int m) {
	++n;
	s[n] = new node{};
	s[n]->apply(s[n - m - 1]);
}

char GetLetter(int p) {
	return Tree.get(s[n], 0, N - 1, p);
}

Compilation message (stderr)

scrivener.cpp: In member function 'void segtree::build(node*&, int, int)':
scrivener.cpp:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   int mid = l + r >> 1;
      |             ~~^~~
scrivener.cpp: In member function 'node* segtree::modify(node*, int, int, int, char)':
scrivener.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int mid = l + r >> 1;
      |             ~~^~~
scrivener.cpp: In member function 'char segtree::get(node*, int, int, int)':
scrivener.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid = l + r >> 1;
      |             ~~^~~

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