这题数据范围真是 5e5 吗？

为什么 5e5 N根号log能过啊，我算了一下已经 3e9 了，还不算各种各样的常数，SPOJ 测评机这么强？