코딩스토리

https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 문제 분석 문제 내용 자체는 간단하다. A의 등수는 A보다 앞에 있는 사람 중 A보다 달리기 평소 실력이 낮은 친구가 몇 명인지를 알아야 구할 수 있다. 가장 간단한 방법은 당연히 브루트포스이다. 각 인원마다 자신보다 앞에 있는 사람들의 평소 실력을 비교해보면 된다. 이때 문제의 N제한이 50만이기 때문에 당연히 1+2+3+...+50만 = O(50만*50만+1/2) = O(천억...?) 이..