IOI 2013 day1 3- 웜뱃(wombats) > 문제은행 : 정보올림피아드&알고리즘




2655 : 웜뱃(wombats)

제한시간
20000 ms   
메모리제한
256 MB   
해결횟수
4 회   
시도횟수
9 회   

문제

브리즈번 시는 돌연변이로 거대해진 웜뱃(호주에 사는 너구리 비슷한 동물)에 장악당했다. 

당신의 임무는 사람들을 구조하는 것이다.

 

브리즈번 시의 도로는 커다란 격자 모양으로 되어 있다.

동서 방향으로 놓인 수평도로는 R 개가 있고, 북쪽에서 남쪽 방향으로 차례로 번호가 0, …, (R - 1) 로 매겨져 있다. 

또한, 남북 방향으로 놓인 수직도로는 C 개가 있고, 서쪽에서 동쪽 방향으로 차례로 번호가 0, …, (C - 1) 로 매겨져 있다. 

다음 그림은 이렇게 번호가 매겨진 도로의 예이다.

 

 

 

 

웜뱃은 북쪽에서부터 쳐들어오고 있고, 사람들은 남쪽으로 도망친다. 

사람들은 가로 방향으로는 어느 쪽이든 움직일 수 있지만, 세로 방향으로는 안전한 방향인 남쪽으로만 움직일 수 있다.

 

수평 도로 P 와 수직 도로 Q 의 교차로는 (P, Q) 로 표현한다. 

두 교차로 사이 세그먼트에는 웜뱃들이 있을 수 있고, 몇 마리의 웜뱃이 있는지는 시간이 흐르면서 변할 수 있다.

여러분의 임무는 북쪽(수평 도로 0 번)의 주어진 교차로에 도착한 사람을 

남쪽(수평 도로 R - 1 번)의 주어진 교차로로 가는 길을 알려주는 것인데, 이 경로를 지날 때 가능한 한 적은 수의 웜뱃을 만나야 한다.

 

먼저, 격자의 크기와 각 도로 세그먼트에 웜뱃이 몇 마리가 있는지가 주어진다. 

다음에는 E 개의 이벤트가 차례로 주어지는데, 각 이벤트는 아래 두 가지 중 하나의 형태이다.
• change : 어떤 도로 세그먼트에 있는 웜뱃의 마릿수가 바뀐다.
• escape : 사람 한 명이 수평 도로 0 번의 주어진 교차로로 도착하고, 

이 사람을 가장 적은 수의 웜뱃을 만나면서 수평 도로 R - 1 의 주어진 교차로로 보내는 경로를 구해야 한다.

 

 

 

 

 

위 그림은 수평도로가 R = 3 개, 수직도로가 C = 4 개, 그리고 각 도로 세그먼트에 웜뱃이 몇 마리가 있는지 주어진 지도의 처음 상황이다. 

다음 순서대로 이벤트가 발생한다고 하자.

 

• 한 사람이 교차로 A = (0, 2) 에 도착해서 교차로 B = (2, 1) 로 도망치고 싶어 한다. 

  이 때 만나는 웜뱃 마릿수의 최솟값은 2 인데, 점선을 따라가면 이를 확인할 수 있다.
• 또 한 사람이 교차로 X = (0, 3) 에 도착해서 교차로 Y = (2, 3) 로 도망치고 싶어 한다. 

  이 때 만나는 웜뱃 마릿수의 최솟값은 7 인데, 또 점선을 따라가면 이를 확인할 수 있다.
• change 이벤트가 두 번 발생한다. 수직 도로 0 의 가장 위 세그먼트에 있는 웜뱃의 수가 5 마리로 바뀌고, 

  수평 도로 1 의 가운데 세그먼트에 있는 웜뱃의 수가 6 마리로 바뀐다. 아래 그림의 동그라미를 친 숫자를 확인해보자.

 

 

 

• 세 번째 사람이 교차로 A = (0, 2) 에 도착해서 교차로 B = (2, 1) 로 도망치고 싶어 한다. 

  이번에는 만나게 되는 웜뱃의 최소 숫자가 5 마리이고, 다시 점선을 따라가면 이를 확인할 수 있다.

 

 


입력형식

첫 줄에 수평도로의 개수 R(2≤R≤5,000), 수직도로의 개수 C(1≤C≤200)가 공백으로 구분하여 들어온다.

그 다음 R줄에는 C-1개의 웜뱃 마릿수 W(0≤W≤1,000)가 들어온다. 

단 C=1 인 경우, 수평 도로에 존재하는 웜뱃의 마릿수를 나타내기 위해서 (줄 2부터 R + 1 까지) 빈 줄들을 사용해야 할 필요는 없다. 

그 다음 R-1줄에는 C개의 웜뱃의 마릿수 W(0≤W≤1,000)가 들어온다. 

그 다음 한 줄에 발생하는 이벤트의 개수 E(1≤E≤20,500)가 들어온다. 

다음 줄부터 각 줄에 이벤트의 정보가 들어온다. 형식은 다음과 같다. 

change 1 p q w ( (p, q) 교차로와 (p, q+1) 교차로사이의 웜뱃의 마릿수가 w로 바뀐다.)

change 2 p q w ( (p, q) 교차로와 (p+1, q) 교차로사이의 웜뱃의 마릿수가 w로 바뀐다.) 

escape 3 v1 v2 (v1에서 v2로 탈출 : 이때 v1의 수평도로는 항상 0, v2의 수평도로는 항상 R-1이다.) 

 

<제약 조건> 

시간 제한 : 20초 

메모리 제한 : 256MB 2 ≤ R ≤ 5,000 1 ≤ C ≤ 200 

change는 최대 500번 escape는 최대 200,000번 

호출 한 세그먼트에 있는 웜뱃의 마릿수는 항상 1,000 이하 

 

[서브태스크] 

서브태스크 1 : C = 1 

서브태스크 2 : R, C ≤ 20 이고 웜뱃의 변경 없다. 

서브태스크 3 : R, C ≤ 100 이고 탈출하는 사람 최대 100번 

서브태스크 4 : C = 2 

서브태스크 5 : C ≤ 100 

서브태스크 6 : (제한없음)

 


출력형식

해당 경로를 지나가는 과정에서 만나는 웜뱃 마릿수의 최솟값을 행으로 구분하여 출력한다.

불가능한 경우 -1을 출력한다.


입력 예

3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1

출력 예

2
7
5


경기도 안양시 동안구 평촌대로 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