[BOJ] 8217번: Meteors

https://www.acmicpc.net/problem/8217

 

Parallel Binary Search를 사용해 풀 수 있는 대표적인 문제입니다. Segment Tree에서의 합이 long long 범위를 초과할 수 있다는 점을 고려하지 않아 계속 틀리다가 맞았네요.(코드의 168번 줄)

 

저처럼 쿼리를 mid 기준으로 정렬하는 것 보다는 mid의 값이 1에서 $Q$ 사이이므로 vector를 $Q$개 만들어두는 식으로 구현하면 $log N$을 줄일 수 있습니다.

 

https://github.com/blisstoner/BOJ/blob/master/8217.cpp