IOI 2010 Day 1 Task 3 : Quality Of Living
dovelet 링크 R*C 크기의 격자가 있고, 이 격자에 각각 숫자가 있다(1부터 (R*C)까지 unique하게). 이제 여기서 H*W 크기의 임의의 직사각형을 잡으면, 그 안에 있는 숫자들의 median(중간값)을 구할 수 있다. 그러면 약 (R-H+1)*(C-W+1) 가지의 직사각형이 나오고 각각의 median이 나오겠지? 그 중 최댓값을 구하는 문제이다. (1≤H≤R≤3000, 1≤W≤C≤3000) 새로운 수가 들어왔다 나갔다 하면서 Median이 계속 변하는 문제는 O(lgN)만에 새로운 값을 추가하고, O(1)만에 중간값을 알아내고, O(1)만에 값을 삭제할 수 있다. 그래서 이 문제의 경우, H*W 크기의 격자를 전체 격자 위에서 ㄹ자 모양으로 움직이도록 밀면 모든 경우의 median을 따질..
2014. 8. 12. 10:05