The J-th Number
2020. 12. 17. 01:49ㆍPS/Problem Solving
10641번: The J-th Number
You are given N empty arrays, t1,…,tn. At first, you execute M queries as follows. add a value v to array ti (a ≤ i ≤ b) Next, you process Q following output queries. output the j-th number of the sequence sorted all values in ti (x ≤ i ≤ y)
www.acmicpc.net
진짜 너무 화났지만 재밌는 문제다.
PBS가 무엇인지는 이 글 참고.
Range Update, Range Sum Query가 필요하므로 당연히 처음에 Lazy Propagation을 떠올렸다. 하지만 실행 시간 면에서 펜윅 2개 쓰는게 훨씬 빠를거라 생각해서 펜윅으로 구현했다. 그 덕분에 레이지로 구현했을 때는 처리해주지 않아도 될 개구간/폐구간 문제를 고려하지 않아 2시간 디버깅 시간이 생겼다.
항상 겪는 문제지만 일단 문제를 해결하자. 실행시간/메모리 효율 향상 욕심에 선택하는 것들이 문제 해결에 대한 속도를 낮추고 있다. 이런 경우 항상 정말 중요한 로직을 생각하는 것에 대한 귀찮음이 동반된다. 맞왜틀을 겪기 십상. 오늘 배운 것을 기억하자.
728x90
'PS > Problem Solving' 카테고리의 다른 글
| 프로그래밍으로 수학하기 (0) | 2020.12.29 |
|---|---|
| 제 1회 세종정보올림피아드 (0) | 2020.12.20 |
| 병렬이분탐색 & 최소신장트리 (0) | 2020.12.16 |
| Codeforces Round #690 (Div. 3) (0) | 2020.12.16 |
| 알고리즘 프로그램 (0) | 2020.12.15 |