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