TopCoder

User's AC Ratio

84.2% (32/38)

Submission's AC Ratio

38.3% (69/180)

Description

愛吃冰塊的大陸人喜歡收藏歷史悠久的冰塊。

某天大陸人網購了一塊$1 \times 2$的清朝冰塊,開心的準備放入他的收藏盒。然而,一打開盒子他就遇到了一個難題,就是他不知道要放哪個位置比較合適,尤其是收藏盒中已經有許多奇形怪狀的冰塊,讓這個問題更複雜了。
具有預知能力的大陸人算準了你現在面前有一台電腦,所以請(ㄨㄟ)求(ㄒㄧㄝˊ)你幫他算出指定範圍內,他有幾種放冰塊的方式。

注意,冰塊可以旋轉!(當然,只能放直的或橫的,不能放斜的)

Input Format

第一行包含兩個正整數$R, C$,表示冰塊盒的大小。
接著有$R$行,每行有$C$個數字,$1$表示該格是空的、$0$表示該格上有冰塊。
再來有一個正整數$Q$,表示詢問的數量。
最後有$Q$行,每行有四個整數$r_1 , c_1 , r_2 , c_2$(其中$1 \leq r_1 \leq r_2 \leq R; 1 \leq c_1 \leq c_2 \leq C$),表示詢問的範圍。

對於所有測資,$R \times C \leq 10^ 6; Q\leq 10^ 6$。

子任務(測資) 額外限制 分數
1 (0~4) $R=1$ 35
2 (5~9) $R \times C \leq 10^ 4$、$Q \leq 10^ 3$ 14
3 (5~19) $Q \leq 10^ 4$ 24
4 (0~24) 27

Output Format

針對每筆詢問,輸出冰塊放置的方法數。

Sample Input

7 7
1 1 1 0 1 1 1
0 1 0 0 0 1 0
0 1 0 0 1 1 1
0 0 0 0 0 0 0
1 1 1 0 1 1 1
1 0 1 0 0 1 0
1 1 1 0 1 1 0
2
1 1 3 3
5 1 7 7

Sample Output

4
13

Hints

Sample Input 第一筆詢問(1 1 3 3)的4種放法 : ( "@@" 為放置的冰塊)

@@1 1@@ 1 @1 111
010 010 0 @0 0@0
010 010 0 10 0@0

Problem Source

Problem Set by Ting.H
建國中學106學年度校隊選拔:初試pB

Subtasks

No. Testdata Range Score
1 0~4 35
2 5~9 14
3 5~19 24
4 0~24 27

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3500 131072 262144 1 4
1 3500 131072 262144 1 4
2 3500 131072 262144 1 4
3 3500 131072 262144 1 4
4 3500 131072 262144 1 4
5 1500 131072 262144 2 3 4
6 1500 131072 262144 2 3 4
7 1500 131072 262144 2 3 4
8 1500 131072 262144 2 3 4
9 1500 131072 262144 2 3 4
10 1500 131072 262144 3 4
11 1500 131072 262144 3 4
12 1500 131072 262144 3 4
13 1500 131072 262144 3 4
14 1500 131072 262144 3 4
15 1500 131072 262144 3 4
16 1500 131072 262144 3 4
17 1500 131072 262144 3 4
18 1500 131072 262144 3 4
19 1500 131072 262144 3 4
20 3500 131072 262144 4
21 3500 131072 262144 4
22 3500 131072 262144 4
23 3500 131072 262144 4
24 3500 131072 262144 4