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