fork(1) download 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/c61ee74aaf4152503f5cd8b071814356
  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. 		Paiza.getInstance().resolve(new MyResolver());
  15. 	}
  16. }
  17.  
  18. class MyResolver extends Paiza.Resolver
  19. {
  20.  
  21. 	int[][] table = null;
  22. 	int[][] cache = null;
  23. 	int[] maxWSpace = null;
  24.  
  25. 	@Override
  26. 	public void setHome(Paiza.Home home) {
  27. 		super.setHome(home);
  28.  
  29. 		table = new int[home.getH() + 1][home.getW() + 1];
  30. 		cache = new int[home.getH() + 1][home.getW() + 1];
  31. 		maxWSpace = new int[home.getH() + 1];
  32. 		int[] flag = new int[home.getH() + 1];
  33.  
  34. 		int[][] space2right = new int[home.getH()][home.getW()];
  35. 		int all = 0;
  36.  
  37. 		for (int y = 0; y < home.getH(); y++) {
  38. 			int count = 0;
  39. 			for (int x = home.getW() - 1; x >= 0; x--) {
  40. 				if (home.isSpace(x, y)) {
  41. 					all++;
  42. 					count++;
  43. 					space2right[y][x] = count;
  44. 					int s = 1;
  45. 					int t = count;
  46. 					for (int i = y; i >= 0 && space2right[i][x] > 0; i--) {
  47. 						if (space2right[i][x] < t) {
  48. 							t = space2right[i][x];
  49. 						}
  50. 						table[s][t]++;
  51. 						flag[s] |= t;
  52. 						s++;
  53. 					}
  54. 				} else {
  55. 					count = 0;
  56. 				}
  57. 			}
  58. 		}
  59.  
  60. 		for (int s = 1; s <= home.getH(); s++) {
  61. 			for (int t = Math.min(flag[s], home.getW()); t > 0; t--) {
  62. 				if (table[s][t] > 0) {
  63. 					maxWSpace[s] = t;
  64. 					break;
  65. 				}
  66. 			}
  67. 		}
  68.  
  69. 		cache[1][1] = all + 1;
  70. 	} // setHome()
  71.  
  72. 	@Override
  73. 	public int resolve(Paiza.Widget widget) {
  74. 		int s = widget.getS();
  75. 		int t = widget.getT();
  76. 		if (s > home.getH() || t > home.getW()) {
  77. 			return 0;
  78. 		}
  79. 		if (cache[s][t] > 0) {
  80. 			return cache[s][t] - 1;
  81. 		}
  82. 		int count = 0, end = maxWSpace[s];
  83. 		for (int i = t; i <= end; i++) {
  84. 			count += table[s][i];
  85. 		}
  86. 		cache[s][t] = count + 1;
  87. 		return count;
  88. 	} // resolve()
  89.  
  90. }
  91.  
  92. final class Paiza
  93. {
  94. 	public static abstract class Resolver
  95. 	{
  96. 		protected Paiza.Home home;
  97.  
  98. 		public void setHome(Paiza.Home home) {
  99. 			this.home = home;
  100. 		}
  101.  
  102. 		public abstract int resolve(Paiza.Widget widget);
  103. 	}
  104.  
  105. 	public static Paiza getInstance() throws java.lang.Exception {
  106. 		if (paiza == null) {
  107. 			paiza = new Paiza();
  108. 		}
  109. 		return paiza;
  110. 	}	
  111.  
  112. 	public void resolve(Resolver resolver) {
  113. 		init(resolver);
  114. 		for (Widget widget : widgets) {
  115. 			answer(resolver.resolve(widget));
  116. 		}
  117. 		flush();
  118. 	}
  119.  
  120.  
  121. 	public final class Home
  122. 	{
  123. 		private final int H;
  124. 		private final int W;
  125. 		private int[][] display;
  126. 		private Home(int H, int W) {
  127. 			this.H = H;
  128. 			this.W = W;
  129. 			display = new int[H][W];
  130. 		}
  131.  
  132. 		private void setDisplay(int x, int y, int e) {
  133. 			display[y][x] = e;
  134. 		}
  135.  
  136. 		public int getH() {
  137. 			return H;
  138. 		}
  139.  
  140. 		public int getW() {
  141. 			return W;
  142. 		}
  143.  
  144. 		public boolean isSpace(int x, int y) {
  145. 			return display[y][x] == 0;
  146. 		}
  147. 	}
  148.  
  149. 	public final class Widget
  150. 	{
  151. 		private final int s;
  152. 		private final int t;
  153. 		private Widget(int s, int t) {
  154. 			this.s = s;
  155. 			this.t = t;
  156. 		}
  157.  
  158. 		public int getS() {
  159. 			return s;
  160. 		}
  161.  
  162. 		public int getT() {
  163. 			return t;
  164. 		}
  165. 	}
  166.  
  167. 	private static Paiza paiza = null;
  168.  
  169. 	private Home home;
  170. 	private ArrayList<Widget> widgets;
  171.  
  172. 	private Paiza() throws java.lang.Exception {
  173. 		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  174. 		String[] hw = in.readLine().split(" ");
  175. 		home = new Home(Integer.parseInt(hw[0]), Integer.parseInt(hw[1]));
  176. 		for (int y = 0; y < home.getH(); y++) {
  177. 			String line = in.readLine();
  178. 			for (int x = 0; x < home.getW(); x++) {
  179. 				home.setDisplay(x, y, (int)(line.charAt(x) - '0'));
  180. 			}
  181. 		}
  182. 		int N = Integer.parseInt(in.readLine());
  183. 		widgets = new ArrayList<Widget>(N);
  184. 		for (int i = 0; i< N; i++) {
  185. 			String[] st = in.readLine().split(" ");
  186. 			widgets.add(new Widget(Integer.parseInt(st[0]), Integer.parseInt(st[1])));
  187. 		}
  188. 	}
  189.  
  190. 	private StringBuilder output = null;
  191. 	private static final String NEWLINE = System.getProperty("line.separator");
  192.  
  193. 	private void init(Resolver resolver) {
  194. 		resolver.setHome(home);
  195. 		output = new StringBuilder(widgets.size() * 6);
  196. 	}
  197.  
  198. 	private void answer(int count) {
  199. 		output.append(count);
  200. 		output.append(NEWLINE);
  201. 	}
  202.  
  203. 	private void flush() {
  204. 		System.out.print(output);
  205. 	}
  206. }
  207.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin 
5 5
00000
00100
00010
10001
10000
3
2 2
1 1
3 2
stdout 
6
20
2
https://ideone.com/WKgDh2
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!