Informatica Online Judge

  2차원 차이 배열 만들기 [1744 / 06D0]

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


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

[koistudy.net (T. HS Jeon 2016)]

Background

크기가 n*m인 2차원 배열 d[][]에 대해

k개의 구간 [(x1, y1), (x2, y2)] 와 u를 입력 받아,

d[x1][y1] = d[x1][y1]+u;
d[x2+1][y2+1] = d[x2+1][y2+1]+u;

d[x1][y2+1] = d[x1][y2+1]-u;
d[x2+1][y1] = d[x2+1][y1]-u;

를 수행한 후, 누적 합을 만들어 출력해보자.

크기가 7*7이고,

4개의 구간 데이터
1 1 2 2 1
2 2 3 3 1
3 3 4 4 1
4 4 5 5 1

가 입력되면

2차원 배열의 상태는
0 0 0 0 0 0 0
0 1 0 –1 0 0 0
0 0 1 0 –1 0 0
0 –1 0 2 0 –1 0
0 0 –1 0 2 0 -1
0 0 0 -1 0 1 0
0 0 0 0 -1 0 1

가 되며

그 누적합을 계산하면 아래와 같다.




0 0 0 0 0 0 0
0 1 1 0 0 0 0
0 1 2 1 0 0 0
0 0 1 2 1 0 0
0 0 0 1 2 1 0
0 0 0 0 1 1 0
0 0 0 0 0 0 0

Input

첫 번째 줄에 배열의 크기 n, m과 구간의 개수 k가 공백을 두고 입력된다.
두 번째 줄부터 k개의 데이터가 공백을 두고 입력된다.
[입력값의 정의역]
1 <= n, m <=1000
1 <= k <= 100
0 < x1 <= x2 < n
0 < y1 <= y2 < m
-1000 <= u <= 1000

Output

n*m 배열의 상태를 출력한 후,
줄을 바꿔 2차원 누적합을 계산해 출력한다.

IO Example

입력
7 7 4
1 1 2 2 1
2 2 3 3 1
3 3 4 4 1
4 4 5 5 1

출력
0 0 0 0 0 0 0
0 1 0 –1 0 0 0
0 0 1 0 –1 0 0
0 –1 0 2 0 –1 0
0 0 –1 0 2 0 -1
0 0 0 -1 0 1 0
0 0 0 0 -1 0 1

0 0 0 0 0 0 0
0 1 1 0 0 0 0
0 1 2 1 0 0 0
0 0 1 2 1 0 0
0 0 0 1 2 1 0
0 0 0 0 1 1 0
0 0 0 0 0 0 0

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