fork(1) download 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/79f911ad242151df16a8e6daa2885979
  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. 	int[][][][] table = null;
  21. 	int[][] cache = null;
  22.  
  23. 	void debug(String key, String str) {
  24. //		System.out.println(key + " : " + str);
  25. 	}
  26.  
  27. 	void printArray(int[][] array, String str) {
  28. 		/*
  29. 		System.out.println("----");
  30. 		System.out.println("Array : " + array.length + "x" + array[0].length + " :: " + str);
  31. 		for (int i = 0; i < array.length; i++) {
  32. 			for (int j = 0; j < array[i].length; j++) {
  33. 				System.out.print(array[i][j] + " ");
  34. 			}
  35. 			System.out.println();
  36. 		}
  37. 		System.out.println("----");
  38. 		*/
  39. 	}
  40.  
  41.  
  42. 	@Override
  43. 	public void setHome(Paiza.Home home) {
  44. 		super.setHome(home);
  45.  
  46. 		table = new int[301][301][][];
  47. 		cache = new int[301][301];
  48.  
  49. 		int[][] temp = table[1][1] = new int[home.getH()][home.getW()];
  50. 		int count = 0;
  51.  
  52. 		for (int y = 0; y < home.getH(); y++) {
  53. 			for (int x = 0; x < home.getW(); x++) {
  54. 				if (home.isSpace(x, y)) {
  55. 					count++;
  56. 				} else {
  57. 					temp[y][x] = 1;
  58. 				}
  59. 			}
  60. 		}
  61.  
  62. 		cache[1][1] = count + 1;
  63. 	}
  64.  
  65. 	@Override
  66. 	public int resolve(Paiza.Widget widget) {
  67. 		if (widget.getS() > home.getH() || widget.getT() > home.getW()) {
  68. 			return 0;
  69. 		}
  70. 		if (cache[widget.getS()][widget.getT()] > 0) {
  71. 			if (table[widget.getS()][widget.getT()] != null) {
  72. 				if (widget.getS() != 1 || widget.getT() != 1) {
  73. 					int f = 0;
  74. 					if (widget.getS() < 300) {
  75. 						if (table[widget.getS() + 1][widget.getT()] != null) {
  76. 							f++;
  77. 						}
  78. 					} else {
  79. 						f++;
  80. 					}
  81. 					if (widget.getT() < 300) {
  82. 						if (table[widget.getS()][widget.getT() + 1] != null) {
  83. 							f++;
  84. 						}
  85. 					} else {
  86. 						f++;
  87. 					}
  88. 					if (f == 2) {
  89. 						table[widget.getS()][widget.getT()] = null;
  90. 					}
  91. 				}
  92. 			}
  93. 			return cache[widget.getS()][widget.getT()] - 1;
  94. 		}
  95. 		return tatami(widget);
  96. 	}
  97.  
  98. 	private int tatami(Paiza.Widget widget) {
  99. 		int e = Math.max(widget.getS(), widget.getT());
  100. 		int tx = 1, ty = 1, x, y;
  101. 		int[][] temp1, temp2;
  102.  
  103. 		debug("tatami", widget.getS() + "," + widget.getT());
  104.  
  105. 		for (int i = 1; i <= e; i++) {
  106. 			tx = 0;
  107. 			ty = 0;
  108.  
  109. 			y = widget.getS();
  110. 			x = widget.getT() - i;
  111.  
  112. 			if (x < 1) {
  113. 				y -= - x + 1;
  114. 				x = 1;
  115. 			}
  116.  
  117. 			while (x <= widget.getT() && y > 0) {
  118. 				debug("seek", y + "," + x);
  119. 				if (table[y][x] != null) {
  120. 					tx = x;
  121. 					ty = y;
  122. 					break;
  123. 				}
  124. 				x++;
  125. 				y--;
  126. 			}
  127.  
  128. 			if (tx != 0) {
  129. 				break;
  130. 			}
  131. 		}
  132.  
  133. 		if (tx == 0 || ty == 0) {
  134. 			tx = 1;
  135. 			ty = 1;
  136. 		}
  137.  
  138. 		printArray(table[ty][tx], "tytx: " + ty + "," + tx);
  139.  
  140. 		if (ty != widget.getS()) {
  141. 			temp1 = table[ty][tx];
  142. 			for (y = ty + 1; y <= widget.getS(); y++) {
  143. 				if (table[y][tx] != null) {
  144. 					printArray(table[y][tx], "skip1: " + y + "," + tx);
  145. 					temp1 = table[y][tx];
  146. 					continue;
  147. 				}
  148. 				temp2 = table[y][tx] = new int[temp1.length - 1][temp1[0].length];
  149. 				for (int i = 0; i < temp2.length; i++) {
  150. 					for (int j = 0; j < temp2[0].length; j++) {
  151. 						temp2[i][j] = temp1[i][j] + temp1[i + 1][j];
  152. 					}
  153. 				}
  154. 				printArray(temp2, "make1: " + y + "," + tx);
  155. 				temp1 = temp2;
  156. 			}
  157. 			ty = widget.getS();
  158. 		}
  159.  
  160. 		if (tx != widget.getT()) {
  161. 			temp1 = table[ty][tx];
  162. 			for (x = tx + 1; x <= widget.getT(); x++) {
  163. 				if (table[ty][x] != null) {
  164. 					printArray(table[ty][x], "skip2: " + ty + "," + x);
  165. 					temp1 = table[ty][x];
  166. 					continue;
  167. 				}
  168. 				temp2 = table[ty][x] = new int[temp1.length][temp1[0].length - 1];
  169. 				for (int i = 0; i < temp2.length; i++) {
  170. 					for (int j = 0; j < temp2[0].length; j++) {
  171. 						temp2[i][j] = temp1[i][j] + temp1[i][j + 1];
  172. 					}
  173. 				}
  174. 				printArray(temp2, "make2: " + ty + "," + x);
  175. 				temp1 = temp2;
  176. 			}
  177. 			tx = widget.getT();
  178. 		}
  179.  
  180. 		temp1 = table[ty][tx];
  181. 		int count = 0;
  182. 		for (int i = 0; i < temp1.length; i++) {
  183. 			for (int j = 0; j < temp1[0].length; j++) {
  184. 				if (temp1[i][j] == 0) {
  185. 					count++;
  186. 				}
  187. 			}
  188. 		}
  189. 		cache[ty][tx] = count + 1;
  190. 		int f = 0;
  191. 		if (ty < 300) {
  192. 			if (table[ty + 1][tx] != null) {
  193. 				f++;
  194. 			}
  195. 		} else {
  196. 			f++;
  197. 		}
  198. 		if (tx < 300) {
  199. 			if (table[ty][tx + 1] != null) {
  200. 				f++;
  201. 			}
  202. 		} else {
  203. 			f++;
  204. 		}
  205. 		if (f == 2) {
  206. 			table[ty][tx] = null;
  207. 		}
  208.  
  209. 		return count;
  210. 	}
  211.  
  212. }
  213.  
  214. final class Paiza
  215. {
  216. 	public static abstract class Resolver
  217. 	{
  218. 		protected Paiza.Home home;
  219.  
  220. 		public void setHome(Paiza.Home home) {
  221. 			this.home = home;
  222. 		}
  223.  
  224. 		public abstract int resolve(Paiza.Widget widget);
  225. 	}
  226.  
  227. 	public static Paiza getInstance() throws java.lang.Exception {
  228. 		if (paiza == null) {
  229. 			paiza = new Paiza();
  230. 		}
  231. 		return paiza;
  232. 	}	
  233.  
  234. 	public void resolve(Resolver resolver) {
  235. 		init(resolver);
  236. 		for (Widget widget : widgets) {
  237. 			answer(resolver.resolve(widget));
  238. 		}
  239. 		flush();
  240. 	}
  241.  
  242.  
  243. 	public final class Home
  244. 	{
  245. 		private final int H;
  246. 		private final int W;
  247. 		private int[][] display;
  248. 		private Home(int H, int W) {
  249. 			this.H = H;
  250. 			this.W = W;
  251. 			display = new int[H][W];
  252. 		}
  253.  
  254. 		private void setDisplay(int x, int y, int e) {
  255. 			display[y][x] = e;
  256. 		}
  257.  
  258. 		public int getH() {
  259. 			return H;
  260. 		}
  261.  
  262. 		public int getW() {
  263. 			return W;
  264. 		}
  265.  
  266. 		public boolean isSpace(int x, int y) {
  267. 			return display[y][x] == 0;
  268. 		}
  269. 	}
  270.  
  271. 	public final class Widget
  272. 	{
  273. 		private final int s;
  274. 		private final int t;
  275. 		private Widget(int s, int t) {
  276. 			this.s = s;
  277. 			this.t = t;
  278. 		}
  279.  
  280. 		public int getS() {
  281. 			return s;
  282. 		}
  283.  
  284. 		public int getT() {
  285. 			return t;
  286. 		}
  287. 	}
  288.  
  289. 	private static Paiza paiza = null;
  290.  
  291. 	private Home home;
  292. 	private ArrayList<Widget> widgets;
  293.  
  294. 	private Paiza() throws java.lang.Exception {
  295. 		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  296. 		String[] hw = in.readLine().split(" ");
  297. 		home = new Home(Integer.parseInt(hw[0]), Integer.parseInt(hw[1]));
  298. 		for (int y = 0; y < home.getH(); y++) {
  299. 			String line = in.readLine();
  300. 			for (int x = 0; x < home.getW(); x++) {
  301. 				home.setDisplay(x, y, (int)(line.charAt(x) - '0'));
  302. 			}
  303. 		}
  304. 		int N = Integer.parseInt(in.readLine());
  305. 		widgets = new ArrayList<Widget>(N);
  306. 		for (int i = 0; i< N; i++) {
  307. 			String[] st = in.readLine().split(" ");
  308. 			widgets.add(new Widget(Integer.parseInt(st[0]), Integer.parseInt(st[1])));
  309. 		}
  310. 	}
  311.  
  312. 	private StringBuilder output = null;
  313. 	private static final String NEWLINE = System.getProperty("line.separator");
  314.  
  315. 	private void init(Resolver resolver) {
  316. 		resolver.setHome(home);
  317. 		output = new StringBuilder(widgets.size() * 6);
  318. 	}
  319.  
  320. 	private void answer(int count) {
  321. 		output.append(count);
  322. 		output.append(NEWLINE);
  323. 	}
  324.  
  325. 	private void flush() {
  326. 		System.out.print(output);
  327. 	}
  328. }
  329.  
Success #stdin #stdout 0.08s 380608KB
comments (?)
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
https://ideone.com/9kQTaF
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!