fork download 
  1. /* paiza POH!vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/c5279346a6edcb14903fd1874bfd9ce0
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. #include <stdio.h>
  7.  
  8. #define SIZE (9000000)
  9.  
  10. char input[SIZE];
  11. char *ptr = input;
  12.  
  13. int getInt(void) {
  14. 	int v = 0;
  15. 	while (*ptr < '0' || *ptr > '9') ++ptr;
  16. 	while (*ptr >= '0' && *ptr <= '9')
  17. 	{
  18. 		v = 10 * v + (int)(*ptr - '0');
  19. 		++ptr;
  20. 	}
  21. 	return v;
  22. }
  23.  
  24. char getChar(void) {
  25. 	while (*ptr < '0' || *ptr > '9') ++ptr;
  26. 	return *ptr++;
  27. }
  28.  
  29. void putInt(int v) {
  30. 	if (v < 10) {
  31. 		putchar('0' + (char)v);
  32. 	} else {
  33. 		putInt(v / 10);
  34. 		putchar('0' + (char)(v % 10));
  35. 	}
  36. }
  37.  
  38. int home[310][310];
  39. int hoge[310][310];
  40. int result[310][310];
  41.  
  42. int startXm[310];
  43. int startYm[310];
  44.  
  45. int main(void) {
  46. 	int H, W, N, s, t;
  47. 	int x, y, c, i, j;
  48. 	int hx, hy, hxe, hye;
  49. 	int count, dy, dx;
  50. 	char ch;
  51.  
  52. 	fread(input, sizeof(char), SIZE, stdin);
  53. 	H = getInt();
  54. 	W = getInt();
  55.  
  56. 	for (y = 0; y < H; ++y) {
  57. 		c = 0;
  58. 		for (x = 0; x < W; ++x) {
  59. 			ch = getChar();
  60. 			if (ch == '0') {
  61. 				c++;
  62. 				if (y) {
  63. 					hoge[y][x] = hoge[y - 1][x] + 1;
  64. 				} else {
  65. 					hoge[y][x] = 1;
  66. 				}
  67. 				startXm[c] = x;
  68. 				startYm[c] = y;
  69. 			} else {
  70. 				c = 0;
  71. 				hoge[y][x] = 0;
  72. 			}
  73. 			home[y][x] = c;
  74. 		}
  75. 	}
  76.  
  77. 	N = getInt();
  78.  
  79.  
  80. 	if (W > H) {
  81. 		for (i = 0; i < N; ++i) {
  82. 			s = getInt();
  83. 			t = getInt();
  84.  
  85. 			if (s > H || t > W) {
  86. 				putchar('0');
  87. 				putchar('\n');
  88. 				continue;
  89. 			}
  90.  
  91. 			if (result[s][t]) {
  92. 				putInt(result[s][t] - 1);
  93. 				putchar('\n');
  94. 				continue;
  95. 			}
  96.  
  97. 			hye = s - 1;
  98. 			hxe = t - 1;
  99. 			count = 0;
  100.  
  101. 			hx = startXm[t];
  102. 			hy = startYm[t];
  103. 			for (j = t + 1; j < 301; ++j) {
  104. 				if (startYm[j] > hy) {
  105. 					hy = startYm[j];
  106. 					hx = startXm[j];
  107. 				}
  108. 			}
  109. 			for (; hy >= hye; --hy) {
  110. 				for (; hx >= hxe; --hx) {
  111. 					if (home[hy][hx] < t) {
  112. 						hx -= home[hy][hx];
  113. 						continue;
  114. 					}
  115. 					if (hoge[hy][hx] < s) {
  116. 						continue;
  117. 					}
  118. 					for (dy = 1; dy < s; ++dy) {
  119. 						y = hy - dy;
  120. 						if (y < 0) {
  121. 							break;
  122. 						}
  123. 						if (home[y][hx] < t) {
  124. 							break;
  125. 						}
  126. 					}
  127. 					if (dy == s) {
  128. 						count++;
  129. 					}
  130. 				}
  131. 				hx = W - 1;
  132. 			}
  133. 			putInt(count);
  134. 			putchar('\n');
  135. 			result[s][t] = count + 1;
  136. 		}
  137. 	} else {
  138. 		for (i = 0; i < N; ++i) {
  139. 			s = getInt();
  140. 			t = getInt();
  141.  
  142. 			if (s > H || t > W) {
  143. 				putchar('0');
  144. 				putchar('\n');
  145. 				continue;
  146. 			}
  147.  
  148. 			if (result[s][t]) {
  149. 				putInt(result[s][t] - 1);
  150. 				putchar('\n');
  151. 				continue;
  152. 			}
  153.  
  154. 			hye = s - 1;
  155. 			hxe = t - 1;
  156. 			count = 0;
  157. 			hx = startXm[t];
  158. 			hy = startYm[t];
  159. 			for (j = t + 1; j < 301; ++j) {
  160. 				if (startXm[j] > hx) {
  161. 					hy = startYm[j];
  162. 					hx = startXm[j];
  163. 				}
  164. 			}
  165. 			for (; hx >= hxe; --hx) {
  166. 				for (; hy >= hye; --hy) {
  167. 					if (home[hy][hx] < t) {
  168. 						continue;
  169. 					}
  170. 					if (hoge[hy][hx] < s) {
  171. 						hy -= hoge[hy][hx];
  172. 						continue;
  173. 					}
  174. 					for (dy = 1; dy < s; ++dy) {
  175. 						y = hy - dy;
  176. 						if (y < 0) {
  177. 							break;
  178. 						}
  179. 						if (home[y][hx] < t) {
  180. 							break;
  181. 						}
  182. 					}
  183. 					if (dy == s) {
  184. 						count++;
  185. 					}
  186. 				}
  187. 				hy = H - 1;
  188. 			}
  189. 			putInt(count);
  190. 			putchar('\n');
  191. 			result[s][t] = count + 1;
  192. 		}
  193. 	}
  194.  
  195. 	return 0;
  196. }
  197.  
Success #stdin #stdout 0s 12216KB
comments (?)
stdin 
5 5
00000
00100
00010
10001
10000
3
2 2
1 1
3 2
stdout 
6
20
2
https://ideone.com/gAXK8m
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!