제출 #398638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398638		hoaphat1	Crayfish scrivener (IOI12_scrivener)	C++17	0 / 100	164 ms	127520 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;
	}
	int 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;

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

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

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

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

컴파일 시 표준 에러 (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 'int segtree::get(node*, int, int, int)':
scrivener.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid = l + r >> 1;
      |             ~~^~~
scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:61:4: warning: operation on 'n' may be undefined [-Wsequence-point]
   61 |  s[++n] = Tree.modify(s[n - 1], 0, N - 1, s[n - 1]->cnt, L);
      |    ^~~
scrivener.cpp:61:4: warning: operation on 'n' may be undefined [-Wsequence-point]
scrivener.cpp:61:4: warning: operation on 'n' may be undefined [-Wsequence-point]
scrivener.cpp:61:4: warning: operation on 'n' may be undefined [-Wsequence-point]

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