1991 . 冰塊盒

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

南ことり
ε=ε=ε=( ￣▽￣) 烙跑囉

User's AC Ratio

82.0% (41/50)

Submission's AC Ratio

36.8% (81/220)

Tags

CKcon 2017-CKcon

Description

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

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

注意，冰塊可以旋轉！（當然，只能放直的或橫的，不能放斜的）

Input Format

第一行包含兩個正整數R,C，表示冰塊盒的大小。
接著有R行，每行有C個數字，1表示該格是空的、0表示該格上有冰塊。
再來有一個正整數Q，表示詢問的數量。
最後有Q行，每行有四個整數r1,c1,r2,c2（其中1≤r1≤r2≤R;1≤c1≤c2≤C），表示詢問的範圍。

對於所有測資，R×C≤106;Q≤106。

子任務（測資） 額外限制 分數
1 (0~4) R=1 35
2 (5~9) R×C≤104、Q≤103 14
3 (5~19) Q≤104 24
4 (0~24) 無 27

Output Format

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

Sample Input 1

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 1

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 (VSS, 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
Submit
Back to Top