사용자 도구

사이트 도구


ps:problems:boj:2517

달리기

ps
링크acmicpc.net/…
출처BOJ
문제 번호2517
문제명달리기
레벨플래티넘 4
분류

Inversion Counting

시간복잡도O(nlogn)
인풋사이즈n<=500,000
사용한 언어Python
제출기록109452KB / 3640ms
최고기록3188ms
해결날짜2021/04/10

풀이

  • 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()

토론

댓글을 입력하세요:
A W H C᠎ H
 
ps/problems/boj/2517.txt · 마지막으로 수정됨: 2021/05/26 10:25 저자 teferi