[백준] 25566. 김밥

newbieski·2022년 11월 24일
0

백준

목록 보기
172/172

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

접근법 - 실패, 시간초과

  • index tree를 3번 사용하는데 시간초과..
  • map을 써서 좌표압축을 해서 그런가 ==> map을 써서 시간초과 나는듯

접근법

  • 뭔데 이렇게 해맸을까
  • 좌표 압축(map안쓰고)
  • r로 정렬 => r보다 작은 것들을 대상으로
  • l 과 r 사이의 합 => l로 업데이트가 되었을 것이므로 l ~ r 사이의 효과
  • l로 update

접근법 - 공식해설

  • https://icpc-sinchon.io/suapc
  • 세그먼트트리 사용하지 않으므로 좌표 압축도 필요 없음
  • l로 정렬하고(r은 역순) 하나씩 탐색
  • 현재의 r보다 기존의 r이 크면 그 곳에 포함 (기존 것이 왼쪽, 오른쪽 모두 포함하니까)
  • 현재의 r이 커지면 새로운 것으로 생각(기존 것이 왼쪽은 커도, 오른쪽은 포함 못함)
profile
newbieski

0개의 댓글