[백준 5419번][플래티넘 3] 북서풍

자료구조를 제외한 라이브러리 최대한 사용하지 않고 문제풀기 (필요하면 직접 코딩)

문제

백준 5419번 북서풍

자료구조 및 알고리즘

• fenwick tree

• sweeping

문제 풀이 및 회고

불가능한 경우를 바로 다 지우고 시작하면 시간이 확실히 많이 줄어들고 모든 경우의 수를 고려하지 않아도 되는 방법을 찾아야 시간이 부족하지 않음

import sys
from collections import Counter

def solution(n: int):
    """
    동쪽, 남쪽 모든 방향으로 항해할 수 있음. 북쪽이나 서쪽으로 항해하는 것은 불가능 => y가 크거나 같고 x가 작거나 같으면 가능함
    동서남북 : [1,0], [-1,0], [0,-1], [0,1]
    :param n:
    :param islands:
    :return:
    """
    answer = 0
    islands_x, islands_y = [], []
    for i in range(n):
        x, y = map(int, input().split())
        islands_x.append([-x, y])
        islands_y.append([y, -x, i])

    islands_y.sort()
    for i in range(n):
        islands_x[islands_y[i][2]][1] = i+1
    islands_x.sort()

    M = 2**16
    fenwick_tree = [0] * (M + 1)
    def updatefen(i):
        nonlocal M, fenwick_tree
        while i <= M:
            fenwick_tree[i] += 1
            i += i & -i

    def sumfen(i):
        SUM = 0
        while i:
            SUM += fenwick_tree[i]
            i -= i & -i
        return SUM

    for x, i in islands_x:
        answer += sumfen(i)
        updatefen(i)
        print(fenwick_tree[:50])

    return answer


if __name__ == "__main__":
    #sys.stdin = open("5419.txt")
    T = int(input())
    for test_case in range(1, T+1):
        n = int(input())
        print(solution(n))