[IOI2012 Day2] Tournament 해법

문제 ↓

tournament.pdf

순서대로 라운드가 진행된다. 라운드 (S[i],E[i])가 진행 되면, 구간 (S[i],E[i])에 있던 실력이 제일 좋은 기사만 남고 나머지는 지워진다. 이렇게 한 명의 기사만 남을 때 까지 라운드는 진행된다.

프로그램 수행 시간을 좀 더 줄이기 위해서, 기사를 지우지 않아도 된다. 라운드에서 살아남는 기사는 가장 실력이 좋은 기사다. 기사들이 탈락하고 새로운 라운드의 진행을, 기사들이 탈락하지 않는 라운드 진행으로 바꿀 수 있다. 따라서 매 라운드 (S[i],E[i])가 실제로 의미하는 초기 상태에서의 구간 (S'[i],E'[i])를 구할 수 있다. 이 때, 구간 (S'[i],E'[i]) 들은 서로 포함 관계에 있거나 아예 만나지 않는다. 즉, 교차하지 않는다.

우리는 이제 새로운 실력 $R$의 기사를 어디에 배치할 것인가를 고민할 수 있다. 새로운 기사가 라운드 (S'[i],E'[i])에서 승리한다고 하자. 그러면 이 기사는 S'[i]에 위치하는 것이 제일 좋으며, 구간을 새로운 기사가 오기 전으로 나타내면 (S'[i],E'[i]-1) 이다. (항상 S'[i] < E'[i]). 따라서 새로운 기사는 구간 (S'[i],E'[i]-1)에서 최대값이 R 보다 작으면 라운드 i에서 이길 수 있음을 의미한다.

이런 관찰들로 Indexed tree를 사용하면 $O(N lg N)$만에 해결할 수 있다.

코드: http://ideone.com/qCb8W4