[BOJ] 15461번: Milk Measurement

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

일단 G는 아무 의미 없음을 쉽게 관찰할 수 있습니다. 편의를 위해 그냥 생산량의 시작점이 0이라고 합시다. milk의 양들을 전부 binary search tree에 넣어둡시다.(C++ STL의 multiset을 이용).  일단 처음엔 대충 N+3개 정도의 0만 tree에 둡니다. 그리고 쿼리는 시간 순으로 미리 정렬해둡니다. 그리고 등장한 소들에 대해, 그 소의 생산량을 저장하는 map 또한 하나 만들어둡니다. 이제 각 쿼리의 ID와 diff에 대해, 우선 해당하는 소의 생산량이 map에 저장되어있는지 살펴봅니다. 없으면 생산량이 0입니다. 그리고나서 leaderboard가 바뀌는지는 아래의 알고리즘으로 파악이 가능합니다.

i) 내가 최대 생산량일 때

그 최대 생산량이 2마리 이상이면 변경

1마리이지만 두번째로 큰 값보다 내가 작거나 같아졌을 경우 변경

ii) 내가 최대 생산량이 아닐 때

내가 최대 생산량 이상이 되면 변경

multiset, map을 이용해 O(lgN)으로 해결이 가능합니다. 매우 여러 번 틀렸는데, multset의 erase가 단 하나만을 지운다고 착각했습니다. 해당하는 원소를 모두 지우는 명령인지 몰랐습니다ㅠㅠ.. 그래도 이렇게나마 알아채서 다행이네요.

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