사용자 도구

사이트 도구


ps:problems:boj:18407

가로 블록 쌓기

ps
링크acmicpc.net/…
출처BOJ
문제 번호18407
문제명가로 블록 쌓기
레벨플래티넘 3
분류

구간 쿼리

시간복잡도O(nlogn)
인풋사이즈n<=100,000
사용한 언어PyPy
제출기록202008KB / 1048ms
최고기록1048ms
해결날짜2021/04/13

풀이

  • 구간 업데이트와 구간 쿼리로 처리되는 문제. 여기에 좌표압축이 추가된 문제.
  • 어떤 구간에 블럭을 놓는 것은, 그 구간의 최대 높이 h를 구한 뒤, 그 구간의 높이를 h+1로 업데이트 하는 것으로 처리된다.
  • 따라서 구간 최대값 쿼리, 구간 assignment 업데이트를 지원하는 lazy segment tree를 이용하면 된다.
  • 좌표의 크기가 최대 1,000,000,000이므로, 좌표 압축이 필수적이다.
  • 좌표압축을 해서구간의 크기를 O(n)으로 축소시키고 나면, 각각의 블럭을 처리하는 데에, O(logn)의 구간쿼리와 O(logn)의 구간업데이트로 처리가 가능하다. 결국 n개의 블럭을 처리하는 데에는 O(nlogn)이고, 좌표압축에 걸리는 O(nlogn)을 추가해도 전체 시간복잡도는 O(nlogn)이 된다.
  • n<100,000 밖에 안되지만 레이지 세그트리 연산이 느려서인지 Python으로는 시간 초과가 발생했다. PyPy로 제출해서 1초정도에 통과.

코드

"""Solution code for "BOJ 18407. 가로 블록 쌓기".

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

This code should be submitted with PyPy3. Python3 gets TLE.
"""

import sys
import itertools
from teflib import segmenttree


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

    pos_set = set(itertools.chain.from_iterable((D, D + W) for W, D in blocks))
    compress_map = {x: i for i, x in enumerate(sorted(pos_set))}
    segtree = segmenttree.LazySegmentTree(
        [0] * len(pos_set),
        merge=max,
        update_value=lambda x, v, size: v,
        update_param=max,
        should_keep_update_order=False
    )
    for W, D in blocks:
        beg = compress_map[D]
        end = compress_map[D + W]
        height = segtree.query(beg, end)
        segtree.range_update(beg, end, height + 1)

    print(segtree.query(0, len(pos_set)))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
M T F V᠎ J
 
ps/problems/boj/18407.txt · 마지막으로 수정됨: 2021/04/30 15:12 저자 teferi