fork download 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/0419cbb09ca38d2f33c8c962cdf39a15
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. import java.util.*;
  7. import java.lang.*;
  8. import java.io.*;
  9.  
  10. class Main
  11. {
  12. 	static int[][] space2left = new int[300][300];
  13. 	static int[][] space2top = new int[300][300];
  14. 	static int[][] result = new int[301][301];
  15. 	static int[] space2leftCount = new int[301];
  16. 	static int[] space2topCount = new int[301];
  17. 	static int[] startPointX = new int[30300];
  18. 	static int[] startPointY = new int[30300];
  19.  
  20. 	public static void main (String[] args) throws java.lang.Exception
  21. 	{
  22.  
  23. 		int[][] space2left = Main.space2left;
  24. 		int[][] space2top = Main.space2top;
  25. 		int[][] result = Main.result;
  26. 		int[] space2leftCount = Main.space2leftCount;
  27. 		int[] space2topCount = Main.space2topCount;
  28. 		int[] startPointX = Main.startPointX;
  29. 		int[] startPointY = Main.startPointY;
  30. 		final String NEWLINE = System.getProperty("line.separator");
  31.  
  32. 		int x, y, i, j, ty, dx, dy, s, t;
  33.  
  34. 		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  35.  
  36. 		String[] hw = in.readLine().split(" ", 2);
  37. 		final int H = Integer.parseInt(hw[0]);
  38. 		final int W = Integer.parseInt(hw[1]);
  39.  
  40. 		int allSpaceCount = 0;
  41.  
  42. 		int startPointCount = 0;
  43.  
  44.  
  45. 		int maxSpace2leftLen = 0;
  46. 		int maxSpace2topLen = 0;
  47.  
  48. 		int[] tempSP2Ty1 = null, tempSP2Ty;
  49.  
  50. 		String[] st;
  51. 		String line;
  52. 		int spaceCount, tempCount, count, seekLength;
  53.  
  54. 		for (y = 0; y < H; y++)
  55. 		{
  56. 			tempSP2Ty = space2top[y];
  57. 			line = in.readLine();
  58. 			spaceCount = 0;
  59. 			for (x = 0; x < W; x++)
  60. 			{
  61. 				if (line.charAt(x) == '0') // 空
  62. 				{
  63. 					spaceCount++;
  64. 					allSpaceCount++;
  65. 					if (y > 0)
  66. 					{
  67. 						tempCount = tempSP2Ty[x] = tempSP2Ty1[x] + 1;
  68. 						if (y == H - 1 && tempCount > 1)
  69. 						{
  70. 							space2topCount[tempCount]++;
  71. 							if (tempCount > maxSpace2topLen)
  72. 							{
  73. 								maxSpace2topLen = tempCount;
  74. 							}
  75. 						}
  76. 					}
  77. 					else // if (y == 0) 
  78. 					{
  79. 						tempSP2Ty[x] = 1;
  80. 					}
  81. 				}
  82. 				else // if (ch == '1') // 埋
  83. 				{
  84. 					if (spaceCount > 1)
  85. 					{
  86. 						startPointX[startPointCount] = x - 1;
  87. 						startPointY[startPointCount] = y;
  88. 						startPointCount++;
  89. 						space2leftCount[spaceCount]++;
  90. 						if (spaceCount > maxSpace2leftLen)
  91. 						{
  92. 							maxSpace2leftLen = spaceCount;
  93. 						}
  94. 					}
  95. 					spaceCount = 0;
  96. 					// space2top[y][x] = 0; // 初期値のまんま
  97. 					if (y > 0) {
  98. 						space2topCount[tempSP2Ty1[x]]++;
  99. 						if (tempSP2Ty1[x] > maxSpace2topLen)
  100. 						{
  101. 							maxSpace2topLen = tempSP2Ty1[x];
  102. 						}
  103. 					}
  104. 				}
  105. 				space2left[y][x] = spaceCount;
  106. 			} // for(x)
  107. 			if (spaceCount > 1)
  108. 			{
  109. 				startPointX[startPointCount] = W - 1;
  110. 				startPointY[startPointCount] = y;
  111. 				startPointCount++;
  112. 				space2leftCount[spaceCount]++;
  113. 				if (spaceCount > maxSpace2leftLen)
  114. 				{
  115. 					maxSpace2leftLen = spaceCount;
  116. 				}
  117. 			}
  118. 			tempSP2Ty1 = tempSP2Ty;
  119. 		} // for(y)
  120.  
  121. 		final int N = Integer.parseInt(in.readLine());
  122.  
  123. 		StringBuilder output = new StringBuilder(N * (6 + NEWLINE.length()));
  124.  
  125. 		for (i = 0; i < N; i++)
  126. 		{
  127. 			st = in.readLine().split(" ", 2);
  128. 			s = Integer.parseInt(st[0]);
  129. 			t = Integer.parseInt(st[1]);
  130.  
  131. 			count = 0;
  132.  
  133. 			if (s <= H && t <= W)
  134. 			{
  135. 				if (result[s][t] > 0)
  136. 				{
  137. 					count = result[s][t] - 1;
  138. 				}
  139. 				else if (s != 1 && t != 1)
  140. 				{
  141. 					for (j = 0; j < startPointCount; j++)
  142. 					{
  143. 						x = startPointX[j];
  144. 						y = startPointY[j];
  145. 						seekLength = space2left[y][x] - t + 1;
  146.  
  147. 						tempSP2Ty = space2top[y];
  148. 						for (dx = 0; dx < seekLength; dx++)
  149. 						{
  150. 							if (tempSP2Ty[x] >= s)
  151. 							{
  152. 								ty = y;
  153. 								for (dy = 0; dy < s; dy++)
  154. 								{
  155. 									if (space2left[ty][x] < t)
  156. 									{
  157. 										break;
  158. 									}
  159. 									ty--;
  160. 								} // for(dy)
  161. 								if (dy == s)
  162. 								{
  163. 									count++;
  164. 								}
  165. 							}
  166. 							x--;
  167. 						} // for(dx)
  168. 					} // for(j)
  169. 				}
  170. 				else if (s != 1)
  171. 				{
  172. 					for (j = s; j <= maxSpace2topLen; j++)
  173. 					{
  174. 						count += space2topCount[j] * (j - s + 1);
  175. 					}
  176. 				}
  177. 				else if (t != 1)
  178. 				{
  179. 					for (j = t; j <= maxSpace2leftLen; j++)
  180. 					{
  181. 						count += space2leftCount[j] * (j - t + 1);
  182. 					}
  183. 				}
  184. 				else // if (s == 1 && t == 1)
  185. 				{
  186. 					count = allSpaceCount;
  187. 				}
  188. 			}
  189. 			output.append(count);
  190. 			output.append(NEWLINE);
  191. 			result[s][t] = count + 1;
  192. 		} // for(i)
  193.  
  194. 		System.out.print(output);
  195.  
  196. 	} // void main([String)
  197.  
  198. } // class Main
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin 
5 5
00000
00100
00010
10001
10000
7
2 2
1 1
3 2
3 2
2 3
3 1
1 3
stdout 
6
20
2
2
1
6
7
https://ideone.com/35F5SH
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!