마법사의 정원 물주기
실버 I의견: 0
마법사 리나는 \(N \times M\) 격자 모양의 정원을 가꾼다. 정원의 각 칸 \((i, j)\)에는 지금까지 물을 준 횟수 \(g_{i,j}\)가 기록되어 있다.
정원사 조수가 \(Q\)개의 질문을 한다. 각 질문은 네 정수 \(r_1, c_1, r_2, c_2\)로 이루어지며, 행 번호 \(r_1\) 이상 \(r_2\) 이하이고 열 번호 \(c_1\) 이상 \(c_2\) 이하인 직사각형 구역 내 모든 칸의 물주기 횟수의 합을 묻는다. 각 질문에 답하여라.
- \(1 \le N, M \le 1\,000\)
- \(1 \le Q \le 100\,000\)
- \(0 \le g_{i,j} \le 100\)
- 각 질문에서 \(1 \le r_1 \le r_2 \le N\), \(1 \le c_1 \le c_2 \le M\)이다.
첫째 줄에 행 수 \(N\), 열 수 \(M\), 질문 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 걸쳐 정원 정보가 주어진다. \(i\)번째 줄에는 \(M\)개의 정수 \(g_{i,1}, g_{i,2}, \dots, g_{i,M}\)이 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 질문 \(r_1\ c_1\ r_2\ c_2\)가 공백으로 구분되어 주어진다.
\(Q\)개의 줄에 걸쳐 각 질문에 해당하는 물주기 횟수의 합을 순서대로 출력한다.
3 3 3
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3
1 1 3 3
12
28
45
\((1,1)\)~\((2,2)\): \(1+2+4+5=12\). \((2,2)\)~\((3,3)\): \(5+6+8+9=28\). \((1,1)\)~\((3,3)\): 전체 합 \(45\).
2 2 3
10 20
30 40
1 1 1 1
1 1 2 2
2 1 2 2
10
100
70
\((1,1)\)~\((1,1)\): \(10\). 전체: \(10+20+30+40=100\). 하단 행: \(30+40=70\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법사의 정원 물주기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법사의 정원 물주기