TopCoder

Thumb a

User's AC Ratio

82.8% (24/29)

Submission's AC Ratio

40.8% (58/142)

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

For Testdata: 0 ~ 4, Score: 35
For Testdata: 5 ~ 9, Score: 14
For Testdata: 5 ~ 19, Score: 24
For Testdata: 0 ~ 24, Score: 27
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3500 131072 65536
1 3500 131072 65536
2 3500 131072 65536
3 3500 131072 65536
4 3500 131072 65536
5 1500 131072 65536
6 1500 131072 65536
7 1500 131072 65536
8 1500 131072 65536
9 1500 131072 65536
10 1500 131072 65536
11 1500 131072 65536
12 1500 131072 65536
13 1500 131072 65536
14 1500 131072 65536
15 1500 131072 65536
16 1500 131072 65536
17 1500 131072 65536
18 1500 131072 65536
19 1500 131072 65536
20 3500 131072 65536
21 3500 131072 65536
22 3500 131072 65536
23 3500 131072 65536
24 3500 131072 65536