의도된 시간복잡도
🔒시간 제한
1.000 S메모리 제한
512 MB제출 수
1정답 수
1정답률
100.000%
문제 설명
남훈 : 그런데 진수, 저번에 푼 문제를 $2$차원 상에서도 풀 수 있을까?
진수 : $2$차원에서?
남훈 : 응. 편의 상 한 변의 길이가 $n$인 정사각형이라고 하자. 맨 왼쪽 위 좌표가 $(y, x) = (1, 1)$이고, 맨 오른쪽 아래 좌표가 $(y, x) = (n, n)$이 되는 거지.
진수 : 쿼리는 어떤식으로 주어져?
남훈 : 네 개의 정수 $y_1, x_1, y_2, x_2$가 주어지는데, $(y_1, x_1)$을 맨 왼쪽 위 좌표, $(y_2, x_2)$를 맨 오른쪽 아래 좌표로 갖는 직사각형에 속한 수들의 합을 구하면 돼.
남훈 : 구체적으로 위와 같은 상황에서 $y_1, x_1, y_2, x_2$ = $1, 2, 3, 3$일 경우 $2+3+7+8+12+13 = 45$를 출력하면 되는거야.
진수 : 음..
입력 설명
첫째 줄에 정사각형의 한 변의 길이 $n$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. $(1 ≤ n ≤ 500; 1 ≤ Q ≤ 100,000)$
둘째 줄부터 $n$개의 줄에 걸쳐 각 행에 속한 $n$개의 수가 공백으로 구분되어 주어진다. 이 수는 $1,000$을 넘지 않는다.
다음으로 $Q$개의 줄에 걸쳐 $y_1, x_1, y_2, x_2$가 공백으로 구분되어 주어진다. 이 좌표가 $n \times n$ 정사각형을 벗어나거나 올바른 직사각형이 아닌 입력은 주어지지 않는다.
출력 설명
쿼리가 주어질 때마다 그에 맞는 답을 차례대로 출력한다.
예시 1
입력
5 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 24 25 26
1 1 1 3
1 2 3 3
2 1 2 3
3 3 5 5
1 1 5 5
출력
6
45
21
174
328힌트 - 아이템
🔒 힌트 아이템을 사용하여 해금 하실 수 있습니다.
기여
만든 사람 : pill27211