레이팅 미적용최근 농장 곳곳에서 저지른 말썽이 미안했던 베시(Bessie)는, 농부 존(Farmer John)이 새로 배송된 건초 더미들을 쌓는 것을 돕기로 했다.
베시는 1..N으로 번호가 붙은 N개 (1 <= N <= 1,000,000, N은 홀수)의 빈 더미에서 시작한다. 그 다음 FJ는 베시에게 K개 (1 <= K <= 25,000)의 지시로 이루어진 수열을 준다. 각 지시는 "A B" 형태이며, 베시가 A..B 범위의 각 더미 맨 위에 건초 더미를 하나씩 추가해야 한다는 뜻이다. 예를 들어 베시가 "10 13"이라는 지시를 받으면, 더미 10, 11, 12, 13 각각에 건초 더미를 하나씩 추가해야 한다.
베시가 지시에 따라 건초 더미 쌓기를 마친 후, FJ는 N개 더미의 높이의 중앙값을 알고 싶어 한다. 즉, 더미들을 정렬했을 때 가운데에 오는 더미의 높이이다 (편리하게도 N이 홀수이므로 이 더미는 유일하다). FJ의 질문에 대한 답을 구하는 것을 베시에게 도와주자.
첫째 줄: 공백으로 구분된 두 정수 N K.
둘째 줄부터 1+K번째 줄까지: 각 줄에 FJ의 지시 하나가 공백으로 구분된 두 정수 A B (1 <= A <= B <= N)의 형태로 주어진다.
베시가 지시를 모두 완료한 후의 더미 높이의 중앙값.
stacking.in · 출력을 쓸 파일 stacking.out7 4
5 5
2 4
4 6
3 51Input details: There are N=7 stacks, and FJ issues K=4 instructions.
Output details: After Bessie is finished, the stacks have heights 0,1,2,3,3,1,0. The median stack height is 1, since 1 is the middle element in the sorted ordering 0,0,1,1,2,3,3.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > January > Bronze