fork download
  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
stdin
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
46
26
29
46
26
6
5
16
26
12
0
0
104
0
0
0
3
5
1
103
0
0
167
0