const구간의 합 구하기(2D) 2초 512MB

문제

N \times N크기의 2차원 배열에 수들이 입력되어 있다.

이 배열의 임의의 구간에 있는 수들의 합을 물어보는 M개의 쿼리에 답하는 프로그램을 작성하시오.

쿼리에 답하는 중간에 배열의 어떤 원소도 값이 변경되지 않는다.

입력

첫 행에 행과 열의 크기 N이 입력된다. ( 1 ≤ N ≤ 1,000)

다음 N개의 행에 걸쳐 N개의 수 A_i가 공백을 구분하여 입력된다. ( -1,000,000 ≤ A_i ≤ 1,000,000)

다음 행에 쿼리의 수 M이 입력된다. ( 1 ≤ M ≤ 1,000,000)

이어서 M개의 행에 쿼리의 정보 sr_i, sc_i, er_i, ec_i가 공백으로 구분되어 입력된다. ( 1≤ sr_i ≤ er_i ≤ N,\ 1≤ sc_i ≤ ec_i ≤ N)

출력

각 쿼리에 대한 결과를 행으로 구분하여 출력한다.

예제1

입력

5
keyboard_return
1space_bar2space_bar3space_bar4space_bar5
keyboard_return
6space_bar7space_bar8space_bar9space_bar0
keyboard_return
-1space_bar2space_bar1space_bar1space_bar1
keyboard_return
5space_bar2space_bar3space_bar1space_bar4
keyboard_return
1space_bar0space_bar1space_bar0space_bar1
keyboard_return
3
keyboard_return
2space_bar1space_bar2space_bar1
keyboard_return
3space_bar3space_bar5space_bar5
keyboard_return
1space_bar1space_bar5space_bar5

출력

6
keyboard_return
13
keyboard_return
67

출처

comkiwer

#3136 upload 4436회 done 1585회 how_to_reg 1218명

const구간의 합 구하기(2D) timer 2초 memory 512MB

문제 picture_in_picture_alt text_fields

입력

출력

예제1

출처

역링크

#3136

const구간의 합 구하기(2D) 2초 512MB

문제