Informatica Online Judge

  건초더미2 [0500 / 01F4]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 91   Total Tried : 487


The Champion of this Problem (C++) : gs15120 - 0ms / 979byte
My Best Submission (C++) : N/A

[]

Background

베시는 탈출한 소들을 막지 못하여 농부 존에게 미안한 마음을 가지고 있었다. 이번에 그 미안함을 달래 줄 수 있는 기회가 생겼다.

이번에 들어오는 배에 엄청난 양의 건초더미가 들어온다. 이 건초를 정리하는 것을 베시는 도와주기로 했다. 이번에 들어올 건초더미를 놓을 수 있는 N개(1부터 N까지 번호가 붙으며 N은 홀수이며 1,000,000을 넘지 않는다.)의 공간을 마련했다.

농부 존은 베시에게 K개(1<=K<=25,000)의 명령을 준다. 각 명령은 "A B"형태로 구성되며, 의미는 A공간에서 B공간까지 건초를 하나씩 더 쌓으라는 의미이다.

예를 들어 농부 존이 베시에게 "10 13"이라고 말한다면 베시는 4개의 건초를 10번, 11번, 12번, 13번 공간에 각각 하나씩 쌓으면 된다.

이 모든 작업이 끝나고 농부존은 그 의 N개의 건초더미 공간의 쌓여 있는 건초더미의 높이들 중 중간값을 알고 싶어졌다.
(만약에 건초더미가 5더미이고 이를 높이 순으로 정렬했을 때 3번째로 높은 건초더미의 높이를 알고싶어졌다는 의미이다. 건초더미의 개수가 홀수이므로 하나로 결정된다.)

베시가 이 값을 찾을 수 있는 프로그램을 작성하여 베시를 도와주자.

Input

첫 번째 줄에 N과 K가 공백으로 구분되어 입력된다.
두 번째 줄부터 K줄에 걸쳐서 존의 명령이 공백으로 구분되어 입력된다.

Output

전체 건초더미의 중간 높이를 출력한다.

IO Example

입력
7 4
5 5
2 4
4 6
3 5

출력
1

*설명 : 베시가 정리를 끝난 후의 각 공간에는 다음과 같이 건초가 쌓여 있다.
0,1,2,3,3,1,0

이를 정렬하면
0,0,1,1,2,3,3

따라서 7개 중 3번째 건초더미의 높이는 1이다.

USACO 2012 January Contest, Bronze Division

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]