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