IOI 2011 day2 2- 코끼리 (Dancing Elephants) > 문제은행 : 정보올림피아드&알고리즘




2528 : 코끼리 (Dancing Elephants)

제한시간
9000 ms   
메모리제한
0 MB   
해결횟수
4 회   
시도횟수
19 회   

문제

N마리의 코끼리가 무대에서 한 줄로 서서 춤을 추는 코끼리 쇼는 파타야에서는 매우 유명하다.

몇 년간의 훈련을 하고 난후 코끼리들은 이 쇼에서 춤을 출 수 있게 된다.

이 쇼는 일련의 동작으로 이루어지며.

각 동작에서는 정확히 한 코끼리만 다른 장소로 이동하며 귀여운 춤을 추는데 제자리에 있을 수도 있다.

쇼 제작자는 전체 쇼의 사진을 포함하는 사진첩을 제작하려 한다.

각 동작마다 모든 코끼리들의 사진을 찍으려고 한다.

쇼가 진행되는 동안 여러 마리의 코끼리들은 같은 장소에 있을 수 있다.

이 경우 같은 장소에 있는 코끼리들은 단순히 다른 코끼리의 뒤에 서 있게 된다.

하나의 카메라는 길이 L의 선분 상에 있는 코끼리들의 사진만 찍을 수 있다(양 끝점 포함).

코끼리들은 무대 전체에 흩어져 있을 수 있으므로,

모든 코끼리들에 대한 스냅사진을 동시에 찍기 위해서는 여러 대의 카메라가 필요할 수도 있다.

예를 들어, L=10이고 무대에서 코끼리들의 위치가 10, 15, 17, 20이라고 하자. 이 순간에는,

아래의 그림과 같이, 하나의 카메라로 모든 코끼리들의 사진을 찍을 수 있다.

(삼각형은 코끼리를 나타내고 사다리꼴은 카메라를 나타낸다.)

  

 

 

그 다음의 동작에서는 15에 있던 코끼리가 32의 위치로 춤추며 이동한다.

이 동작 후의 스냅 사진을 찍기 위해서는 적어도 두 대의 카메라가 필요하다.

 

  

 

그 다음의 동작에서 10에 있던 코끼리가 7의 위치로 이동한다.

이 경우에서는 모든 코끼리들의 사진을 찍기 위해서 세대의 카메라가 필요하다.

 

  

 

당신이 할 일은 각 코끼리들의 동작 후의 코끼리 사진을 찍기 위한 최소의 카메라 개수를 찾아야 한다.

매 동작마다 카메라의 수는 증가할 수도 있고, 감소할 수도 있으며, 변화가 없을 수도 있음에 주의하라.

 

[예제 설명]

 

N=4, L=10 이고, 초기 코끼리의 위치가 다음과 같은 경우를 고려해보자. 

X = 10 15 17 20 

먼저, 함수 init 은 위의 파라미터로 호출될 것이다. 

그 후, 함수 update 는 각 동작마다 한번씩 호출될 것이다. 다음에 함수 호출의 예와 정확한 리턴 값들이 있다: 

 


입력형식

입력의 첫 번째 줄에는 코끼리의 수 N(1≤N≤150,000), 하나의 카메라로 찍을 수 있는 선분의 길이 L(0≤L≤1,000,000,000)과 쇼에서 코끼리가 진행하는 동작의 수 M(1≤M≤150,000)이 들어온다.
두 번째 줄부터 N+1 번째 줄까지 각 코끼리의 처음 위치 K(0≤K≤1,000,000,000)가 오름차순으로 정렬되어 주어진다.
그 다음 N+2 번째 줄부터 N+M+1 번째 줄까지 M 번의 코끼리 동작에 대한 정보 j(1≤j≤M)가 주어지며, 각각의 줄에는 코끼리의 j 번째 동작을 나타내는 jx(0≤jx〈N), jy(0≤jy≤1,000,000,000)가 공백으로 구분하여 들어온다. (jx : 움직일 코끼리의 번호, jy : 동작 후 변경되는 코끼리의 위치 )


출력형식

출력은 M개의 줄로 이루러지며 각 줄에는 코끼리의 동작 후 필요한 카메라의 최소개수를 출력한다.


입력 예

4 10 5
10
15
17
20
2 16
1 25
3 35
0 38
2 0

출력 예

1
2
2
2
3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP