[boj 7626] 직사각형

문제 링크

 

좌표 압축을 하고 스위핑을 하면서 세그먼트 트리를 훝어가며 푸는 문제.

 

아이디어는 나왔는데, 구체화 하는 과정에서 한참을 걸려서, 아래 풀이를 참고해서 풀었다.

대단하신분의 설명과 풀이

 

역시 세상에는 대단한 분들이 많다.

 

내가 오답을 냈던 부분은, 세그먼트 트리의 요소가 영역을 관리했어야 했는데, 점을 관리했던것...

 

import sys
from collections import deque
input = sys.stdin.readline


def U(s, e, l, r, tree_idx, tree, count, val, ys):
    if s > r or e < l: return
    
    if s >= l and e <= r:
        count[tree_idx] += val
        
    else:
        mid = (s+e)>>1
        U(s, mid, l, r, tree_idx<<1, tree, count, val, ys)
        U(mid+1, e, l, r, tree_idx<<1|1, tree, count, val, ys)
        
    if count[tree_idx]:
        tree[tree_idx] = ys[e] - ys[s-1]
    else:
        if s == e: tree[tree_idx] = 0
        else: tree[tree_idx] = tree[tree_idx<<1] + tree[tree_idx<<1|1]


def solve():
    
    coordinates = []
    
    N = int(input())
    
    for _ in range(N):
        coordinates.append(tuple(map(int, input().split())))
    
    xs = list()
    ys = set()
    for x1, x2, y1, y2 in coordinates:
        xs.append((x1, y1, y2, 1))
        xs.append((x2, y1, y2, -1))
        ys.add(y1)
        ys.add(y2)

    xs.sort()    
    ys = list(ys)
    ys.sort()
    
    cnt_to_y = {}
    y_to_cnt = {}
    cnt = 0
    for y in ys:
        cnt += 1
        cnt_to_y[cnt] = y
        y_to_cnt[y] = cnt
        
    tree = [0] * (4 * cnt + 1)
    count = [0] * (4 * cnt + 1)
    
    ans = 0
    
    prev, y1, y2, _ = xs[0]
    
    U(1, cnt-1, y_to_cnt[y1], y_to_cnt[y2]-1, 1, tree, count, 1, ys)
    
    for idx in range(1, len(xs)):
        x, y1, y2, flag = xs[idx]
        
        ans += (x - prev) * tree[1]
        prev = x
        U(1, cnt-1, y_to_cnt[y1], y_to_cnt[y2]-1, 1, tree, count, flag, ys)
        
    print(ans)
    
    return


def main():
    solve()
    
    return


if __name__ == "__main__":
    main()

파이썬 시간초과는 서럽다...