대회 공식 솔루션을 포함해서 확인 가능한 모든 제출된 풀이가 O(N^2) 시뮬레이션 코드로 되어 있어요.

그리고 실제 데이터에는 N이 100까지밖에 들어있지 않은데(30449053, 공식 데이터), O(N^2)보다 빠른 풀이가 있더라도 다른 문제를 만드는 것이 맞을 것 같네요.