덩치

• 2-tuple의 리스트가 주어졌을때, 각각에 대해서 도미넌트한 튜플의 갯수를 세는 문제. 북서풍와 거의 유사한 문제이고, 관련 풀이는 Inversion Counting을 참고하면 된다.
• 하지만 북서풍이 플래티넘 난이도인것에 비해 이 문제는 실버인 이유는, n이 최대 50밖에 안돼서, 그냥 O(n^2) 알고리즘으로 돌려도 충분하기 때문. 여기에서는 정해인 O(nlogn) 풀이만 올렸지만, O(n^2) 알골리즘이 코드가 훨씬 간단한것은 당연하고, 실행시간에서조차도 펜윅트리로 구현하는 O(nlogn) 알고리즘 보다도 더 빨리 실행된다.

"""Solution code for "BOJ 7568. 덩치".

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

Tags: [OrderStatisticTree]
"""

from teflib import fenwicktree


def main():
    N = int(input())
    heights, weights = [], []
    for _ in range(N):
        x, y = [int(x) for x in input().split()]
        weights.append(x)
        heights.append(y)

    ost = fenwicktree.OrderStatisticTree(max(heights) + 1)
    ranks = [None] * N
    order_by_weight = sorted(range(N), key=lambda i: (-weights[i], heights[i]))
    for i in order_by_weight:
        h = heights[i]
        ranks[i] = ost.size() - ost.count_less_than(h) - ost.count(h) + 1
        ost.add(h)

    print(*ranks)


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.OrderStatisticTree