fork download
copy 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/60c96cab5eb14042b7e8df20c2b99382
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. #include <stdio.h>
  7.  
  8. #define OUTPUTSIZE (600000)
  9. char output[OUTPUTSIZE];
  10. char *optr = output;
  11.  
  12. void putInt(int v) {
  13. 	if (v < 10) {
  14. 		*optr = '0' + (char)v;
  15. 		++optr;
  16. 	} else {
  17. 		putInt(v / 10);
  18. 		*optr = '0' + (char)(v % 10);
  19. 		++optr;
  20. 	}
  21. }
  22.  
  23. void putNewline(void) {
  24. 	*optr = '\n';
  25. 	++optr;
  26. }
  27.  
  28. #define BUFSIZE (900000)
  29. char buf[BUFSIZE];
  30. char *ptr = buf;
  31.  
  32. int getInt(void) {
  33. 	int v = 0;
  34. 	while (*ptr < '0' || *ptr > '9') ++ptr;
  35. 	while (*ptr >= '0' && *ptr <= '9') {
  36. 		v = 10 * v + (int)(*ptr - '0');
  37. 		++ptr;
  38. 	}
  39. 	return v;
  40. }
  41.  
  42. char getChar(void) {
  43. 	while (*ptr < '0' || *ptr > '9') ++ptr;
  44. 	return *ptr++;
  45. }
  46.  
  47. int space2left[300][300];
  48. int space2top[300][300];
  49. int result[301][301];
  50. int space2leftCount[301];
  51. int space2topCount[301];
  52. int startPointX[30300];
  53. int startPointY[30300];
  54. int startPointCount;
  55. int allSpaceCount;
  56. int maxSpace2leftLen;
  57. int maxSpace2topLen;
  58. int seekLength;
  59.  
  60. int spaceCount, tempCount, count;
  61.  
  62. int *tempSP2Ty;
  63. int *tempSP2Ty1;
  64.  
  65. int main(void) {
  66. 	int H, W, N, s, t, i, j, x, y, dx, ty, dy;
  67.  
  68. 	fread(buf, sizeof(char), BUFSIZE, stdin);
  69.  
  70. 	H = getInt();
  71. 	W = getInt();
  72.  
  73. 	for (y = 0; y < H; ++y) {
  74. 		spaceCount = 0;
  75. 		tempSP2Ty = space2top[y];
  76. 		for (x = 0; x < W; ++x) {
  77. 			if (getChar() == '0') {
  78. 				++spaceCount;
  79. 				++allSpaceCount;
  80. 				if (y > 0) {
  81. 					tempCount = tempSP2Ty[x] = tempSP2Ty1[x] + 1;
  82. 					if (y == H - 1 && tempCount > 1) {
  83. 						++space2topCount[tempCount];
  84. 						if (tempCount > maxSpace2topLen) {
  85. 							maxSpace2topLen = tempCount;
  86. 						}
  87. 					}
  88. 				} else {
  89. 					tempSP2Ty[x] = 1;
  90. 				}
  91. 			} else {
  92. 				if (spaceCount > 1) {
  93. 					startPointX[startPointCount] = x - 1;
  94. 					startPointY[startPointCount] = y;
  95. 					++startPointCount;
  96. 					++space2leftCount[spaceCount];
  97. 					if (spaceCount > maxSpace2leftLen) {
  98. 						maxSpace2leftLen = spaceCount;
  99. 					}
  100. 				}
  101. 				spaceCount = 0;
  102. 				tempSP2Ty[x] = 0;
  103. 				if (y > 0 && tempSP2Ty1[x] > 1) {
  104. 					++space2topCount[tempSP2Ty1[x]];
  105. 					if (tempSP2Ty1[x] > maxSpace2topLen) {
  106. 						maxSpace2topLen = tempSP2Ty1[x];
  107. 					}
  108. 				}
  109. 			}
  110. 			space2left[y][x] = spaceCount;
  111. 		}
  112. 		if (spaceCount > 1) {
  113. 			startPointX[startPointCount] = W - 1;
  114. 			startPointY[startPointCount] = y;
  115. 			++startPointCount;
  116. 			++space2leftCount[spaceCount];
  117. 			if (spaceCount > maxSpace2leftLen) {
  118. 				maxSpace2leftLen = spaceCount;
  119. 			}
  120. 		}
  121. 		tempSP2Ty1 = tempSP2Ty;
  122. 	}
  123.  
  124. 	N = getInt();
  125.  
  126. 	for (i = 0; i < N; ++i) {
  127. 		s = getInt();
  128. 		t = getInt();
  129. 		count = 0;
  130.  
  131. 		if (s <= H && t <= W) {
  132. 			if (result[s][t]) {
  133. 				count = result[s][t] - 1;
  134. 			} else {
  135. 				if (s != 1 && t != 1) {
  136. 					for (j = 0; j < startPointCount; ++j) {
  137. 						x = startPointX[j];
  138. 						y = startPointY[j];
  139. 						seekLength = space2left[y][x] - t + 1;
  140.  
  141. 						tempSP2Ty = space2top[y];
  142. 						for (dx = 0; dx < seekLength; ++dx) {
  143. 							if (tempSP2Ty[x] >= s) {
  144. 								ty = y;
  145. 								for (dy = 0; dy < s; ++dy) {
  146. 									if (space2left[ty][x] < t) {
  147. 										break;
  148. 									}
  149. 									--ty;
  150. 								}
  151. 								if (dy == s) {
  152. 									++count;
  153. 								}
  154. 							}
  155. 							--x;
  156. 						}
  157. 					}
  158. 				} else if (s != 1) {
  159. 					for (j = s; j <= maxSpace2topLen; ++j) {
  160. 						count += space2topCount[j] * (j - s + 1);
  161. 					}
  162. 				} else if (t != 1) {
  163. 					for (j = t; j <= maxSpace2leftLen; ++j) {
  164. 						count += space2leftCount[j] * (j - t + 1);
  165. 					}
  166. 				} else {
  167. 					count = allSpaceCount;
  168. 				}
  169. 				result[s][t] = count + 1;
  170. 			}
  171. 		}
  172.  
  173. 		putInt(count);
  174. 		putNewline();
  175. 	}
  176.  
  177. 	fwrite(output, sizeof(char), (int)optr - (int)output, stdout);
  178. 	return 0;
  179. }
  180.  
Success #stdin #stdout 0s 5056KB
comments (?)
stdin
copy 
8 30
000000100010011000000100010011
001001100001010000010001010101
000010001010101000010001001010
100000001001100000000100010011
100000001010011000010001010101
000010001001010000010001001010
110000111010101000000100010011
000010001010100000010001010100
24
2 2
2 3
3 2
2 2
2 3
3 4
4 4
3 3
2 3
4 3
300 12
53 299
1 2
4 7
3 10
10 3
2 5
4 4
8 4
2 1
8 8
8 5
1 1
6 7
7 1
4 2
2 7
4 1
1 8
3 3
4 4
5 5
2 2
3 2
3 4
stdout
copy 
46
26
29
46
26
6
5
16
26
12
0
0
104
0
0
0
3
5
1
103
0
0
167
0
https://ideone.com/Mng0Is
language:
C (gcc 8.3)
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!