달리기

• Inversion Counting을 응용한 문제.
• inversion관계에 있는 (i,j) 갯수의 총합을 구하는 것이 아니라, 각 j별로 갯수를 구해주면 된다.
• Inversion Counting에 설명했듯이, 머지소트를 응용한 방식과 Order Statistic Tree를 이용한 방식 모두 가능하지만, Order Statistic Tree를 사용한 방식이 더 빨라서 이쪽만 코드를 수록했다.
  • 좌표압축을 추가로 해줘야 하는 페널티가 있음에도, Order Statistic Tree는 약 3600ms로 머지소트 방식의 약 4000ms보다 빨랐다
• 시간 복잡도는 O(nlogn)이다.

"""Solution code for "BOJ 2517. 달리기".

- Problem link: https://www.acmicpc.net/problem/2517
- Solution link: http://www.teferi.net/ps/problems/boj/2517
"""

import sys
from teflib import fenwicktree


def main():
    N = int(sys.stdin.readline())
    speeds = [int(sys.stdin.readline()) for _ in range(N)]

    ost = fenwicktree.OrderStatisticTree(N)
    rank_by_speed = {x: i for i, x in enumerate(sorted(speeds, reverse=True))}
    for speed in speeds:
        rank = rank_by_speed[speed]
        print(ost.count_less_than(rank) + 1)
        ost.add(rank)


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.OrderStatisticTree