Tags

17 pages

Coordinate Compression

[Algorithm] cpp 백준 10076번: 휴가 - 최적 풀이

IOI 2014 Holiday(휴가) 최적 풀이. 선형 도시에서 하루에 이동 또는 방문만 가능한 제약에서 방문 관광지 수를 최대화한다. 이동은 한 번의 방향 전환만 해도 충분하다는 관찰 아래 [l,r] 구간을 잡고 체류 가능일 g(l,r)을 계산한다. 분할정복+세그먼트 트리로 상위 k 합을 빠르게 질의하여 O(N log^2 N)로 해결한다. 경계·중복·음수 k 처리와 좌우 반전까지 구현 체크리스트 포함.
[Algorithm] cpp 백준 10076번: 휴가 - 최적 풀이

[Algorithm] cpp 백준 11012번: Egg - 2D 직사각형 쿼리 스위핑+BIT

n개의 점과 m개의 직사각형 [l,r]×[b,t]가 주어질 때, 각 직사각형 안의 점 개수를 모두 합한 값을 구한다. x를 기준으로 오프라인 스위핑을 수행하고, y는 좌표 압축 후 펜윅 트리(Fenwick Tree)로 누적 빈도를 관리한다. 쿼리는 (r,+1),(l-1,−1) 이벤트로 분해해 포함-배제를 구현하여 총합을 O((n+m) log n)에 계산한다. 64비트 누적, 경계(b=0) 처리, 중복 좌표 대응을 주의한다.
[Algorithm] cpp 백준 11012번: Egg - 2D 직사각형 쿼리 스위핑+BIT

[Algorithm] cpp 백준 16670번: King Kog의 접견실 - 세그먼트 트리

기사들의 방문(도착 시각 t, 소요 d)이 실시간으로 추가/취소되는 상태에서 공주가 시각 t에 도착했을 때의 대기 시간을 즉시 구합니다. 누적 처리량 P(t)와 선형 시간 t를 결합한 백로그 공식 W(t) = (P(t) - t) - min_{u≤t}(P(u) - u) 를 활용하고, 좌표 압축 + 지연 전파 세그먼트 트리로 접수/취소는 suffix 가산, 질의는 점/구간 최소를 O(log N)에 처리해 q ≤ 3e5를 안정적으로 통과합니다.
[Algorithm] cpp 백준 16670번: King Kog의 접견실 - 세그먼트 트리

[Algorithm] cpp 백준 16977번: 히스토그램에서 가장 큰 직사각형과 쿼리 - PBS+세그트리

히스토그램의 구간 [l,r]에서 너비 w가 고정일 때 최대 넓이는 길이 w 윈도우의 최솟값을 최대화하는 문제입니다. 높이 좌표압축과 임계값 단조성을 이용해 병렬 이분탐색을 수행하고, 세그먼트 트리(연속 1의 최댓값)로 검증하여 각 쿼리를 빠르게 해결합니다. 엣지 케이스와 실수 포인트까지 점검합니다.
[Algorithm] cpp 백준 16977번: 히스토그램에서 가장 큰 직사각형과 쿼리 - PBS+세그트리