[BOJ] 8876번: 바자와 샤자(IOI'13 Game)

https://www.acmicpc.net/problem/8876

 

IOI'13 Game 문제입니다. 굉장히 빡세다는 얘기만 듣고 구현해볼 엄두를 못냈는데, 큰 마음먹고 구현을 했습니다. 메모리를 절약하기 위해 pointer를 들고가는 대신 left, right index를 가져갔습니다.

 

2d segment tree를 처음 짜봤는데 굉장히 오류가 많아 열심히 뜯어고쳐서 간신히 맞았네요. 이걸 어떻게 고등학생때 풀 수 있는지 경이롭네요. 역시 국대는 넘사인 것 같습니다,,,

 

https://github.com/blisstoner/BOJ/blob/master/8876.cpp