yony1995   2년 전

세그먼트 트리는 쓰지 않았습니다.

2개의 배열에 합과 항목을 따로 저장한 뒤 항목만 갱신하고

업데이트 내용을 vector에 저장하는 방식을 이용했습니다.

edenooo   2년 전

59번째 라인 c가 idx보다 크거나 같은지는 확인했지만, b가 idx보다 작거나 같은지는 확인하지 않았네요.

edenooo   2년 전

그리고 저렇게 짜면 최악의 경우 O(MN)으로 시간 초과가 나오지 않을까요?

yony1995   2년 전

if (c < vec[j].first || b > vec[j].first) continue;

이런식으로 수정하여 정답입니다 띄웠습니다. b가 큰경우를 간과했네요.

감사합니다. 다행히 시간초과가 뜨진 않아요.

djm03178   2년 전

O(MN)이라는 이야기를 듣고 데이터를 추가해야 하나 달려와봤는데, 안타깝게도 O(N+MK)인 것 같네요.

edenooo   2년 전

@djm03178 네 제가 잘못 봤어요 ㅠㅜ

댓글을 작성하려면 로그인해야 합니다.