やっぱり遅いのかScannerは

個人的にとても良問だと思った問題であるところのPKU2559ですが、これってO(n*log(n))で通るのね。
てっきりO(n)でしか通らないと思っていたが、Scannerを使わなければO(n*log(n))が可能になるらしい。log(n)を定数倍としてカバーしてしまうだけのScannerはやはり恐ろしい。
ちなみに、見てもらえば分かりますが時間的にはコレくらい違います。一行丸々読み込んだりして処理している関係で、メモリの消費量はBufferedReaderのほうが大きいですが、アルゴリズムは一切変えてません。後はCode Lengthですが、Scannerの使用をコメントアウトしてBufferedReader使用に切り替えたので、当然ながら長くなってます。