fork(1) download 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/97007b72765944290b4b49f01c521e17
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. import java.util.*;
  7. import java.lang.*;
  8. import java.io.*;
  9.  
  10.  
  11. class Main
  12. {
  13. 	public static void main (String[] args) throws java.lang.Exception
  14. 	{
  15. 		BufferedReader in = new BufferedReader(
  16. 			new InputStreamReader(System.in));
  17.  
  18. 		String[] hw = in.readLine().split(" ");
  19. 		int H = Integer.parseInt(hw[0]); // ホーム画面縦の区画数
  20. 		int W = Integer.parseInt(hw[1]); // ホーム画面横の区画数
  21.  
  22. 		int[][] home = new int[H][W];
  23.  
  24. 		for (int y = 0; y < H; y++)
  25. 		{
  26. 			String line = in.readLine();
  27. 			for (int x = 0; x < W; x++)
  28. 			{
  29. 				home[y][x] = (int)(line.charAt(x) - '0');
  30. 			}
  31. 		}
  32.  
  33. 		int N = Integer.parseInt(in.readLine()); // ウィジェット数
  34.  
  35. 		WidgetTree tree = new WidgetTree();
  36. 		Set<Widget> set = new HashSet<Widget>(N);
  37. 		Widget[] list = new Widget[N];
  38.  
  39. 		for (int i = 0; i < N; i++)
  40. 		{
  41. 			String[] st = in.readLine().split(" ");
  42. 			int s = Integer.parseInt(st[0]); // ウィジェットの縦サイズ
  43. 			int t = Integer.parseInt(st[1]); // ウィジェットの横サイズ
  44.  
  45. 			list[i] = Widget.getWidget(s, t);
  46.  
  47. 			if (s <= H && t <= W)
  48. 			{
  49. 				if (set.add(list[i]))
  50. 				{
  51. 					tree.add(list[i]);
  52. 				}
  53. 			}
  54.  
  55. 		}
  56.  
  57. 		tree.calc(H, W, home);
  58.  
  59. 		// System.out.println(tree);
  60.  
  61. 		for (Widget widget : list)
  62. 		{
  63. 			System.out.println(widget.getAnswer());
  64. 		}
  65.  
  66. 	} // end of main(String[])
  67. }
  68.  
  69.  
  70. class Widget
  71. {
  72. 	private static Widget[] pool = new Widget[90604];
  73.  
  74. 	public static Widget getWidget(int s, int t)
  75. 	{
  76. 		int index = s * 301 + t;
  77. 		if (pool[index] == null)
  78. 		{
  79. 			pool[index] = new Widget(s, t);
  80. 		}
  81. 		return pool[index];
  82. 	}
  83.  
  84. 	private final int s;
  85. 	private final int t;
  86. 	private int answer = 0;
  87. 	private Widget(int s, int t)
  88. 	{
  89. 		this.s = s;
  90. 		this.t = t;
  91. 	}
  92.  
  93. 	public int getS()
  94. 	{
  95. 		return s;
  96. 	}
  97.  
  98. 	public int getT()
  99. 	{
  100. 		return t;
  101. 	}
  102.  
  103. 	public int getAnswer()
  104. 	{
  105. 		return answer;
  106. 	}
  107.  
  108. 	public int setAnswer(int answer)
  109. 	{
  110. 		this.answer = answer;
  111. 		return answer;
  112. 	}
  113.  
  114. 	@Override
  115. 	public int hashCode()
  116. 	{
  117. 		return s * 301 + t;
  118. 	}
  119.  
  120. 	@Override
  121. 	public boolean equals(Object obj)
  122. 	{
  123. 		if (this == obj) return true;
  124. 		if (obj == null) return false;
  125. 		if (this.getClass().equals(obj.getClass()) == false) return false;
  126. 		Widget widget = (Widget)obj;
  127. 		return this.s == widget.s && this.t == widget.t;
  128. 	}
  129.  
  130. 	@Override
  131. 	public String toString()
  132. 	{
  133. 		return "[" + s + "," + t + "]";
  134. 	}
  135.  
  136. 	public enum Extend
  137. 	{
  138. 		S_PARENT, S_CHILD, T_PARENT, T_CHILD,
  139. 		SAME, IMPOSSIBLE, PRE_T_CHILD, PRE_S_CHILD,
  140. 		PRE_PARENT
  141. 	}
  142.  
  143. 	public Extend getExtend(Widget widget)
  144. 	{
  145. 		if (this.s == widget.s && this.t == widget.t)
  146. 		{
  147. 			return Extend.SAME;
  148. 		}
  149. 		if (this.s == widget.s)
  150. 		{
  151. 			if (this.t < widget.t)
  152. 			{
  153. 				return Extend.T_CHILD;
  154. 			}
  155. 			return Extend.T_PARENT;
  156. 		}
  157. 		if (this.t == widget.t)
  158. 		{
  159. 			if (this.s < widget.s)
  160. 			{
  161. 				return Extend.S_CHILD;
  162. 			}
  163. 			return Extend.S_PARENT;
  164. 		}
  165. 		if (this.s < widget.s && this.t < widget.t)
  166. 		{
  167. 			if (widget.s < widget.t)
  168. 			{
  169. 				return Extend.PRE_T_CHILD;
  170. 			}
  171. 			return Extend.PRE_S_CHILD;
  172. 		}
  173. 		if (this.s > widget.s && this.t > widget.t)
  174. 		{
  175. 			return Extend.PRE_PARENT;
  176. 		}
  177. 		return Extend.IMPOSSIBLE;
  178. 	}
  179. }
  180.  
  181. class WidgetTree
  182. {
  183. 	private class Node
  184. 	{
  185. 		final Widget widget;
  186. 		Node t_child = null;
  187. 		Node s_child = null;
  188. 		Queue<Node> pre_s_child = null;
  189. 		Queue<Node> pre_t_child = null;
  190. 		Node(Widget widget)
  191. 		{
  192. 			this.widget = widget;
  193. 		}
  194.  
  195. 		public int childrenCount()
  196. 		{
  197. 			int c = (t_child != null ? 1 : 0)
  198. 					+ (s_child != null ? 1: 0);
  199. 			if (pre_s_child != null)
  200. 			{
  201. 				c += pre_s_child.size();
  202. 			}
  203. 			if (pre_t_child != null)
  204. 			{
  205. 				c += pre_t_child.size();
  206. 			}
  207. 			return c;
  208. 		}
  209.  
  210. 		@Override
  211. 		public String toString()
  212. 		{
  213. 			return "<" + widget + ";" + t_child 
  214. 				+ ";" + s_child + ";(" 
  215. 				+ pre_t_child + ");(" + pre_s_child + ")>";
  216. 		}
  217. 	}
  218.  
  219. 	private Node root = new Node(Widget.getWidget(1,1));
  220.  
  221. 	@Override 
  222. 	public String toString()
  223. 	{
  224. 		return root.toString();
  225. 	}
  226.  
  227. 	private enum Family { T_FAMILY, S_FAMILY }
  228.  
  229. 	private Node setFamily(Node parent, Node child, Family family)
  230. 	{
  231. 		if (parent == null || child == null || family == null)
  232. 		{
  233. 			return parent;
  234. 		}
  235. 		switch (family)
  236. 		{
  237. 			case T_FAMILY:
  238. 				parent.t_child = child;
  239. 				break;
  240. 			case S_FAMILY:
  241. 				parent.s_child = child;
  242. 				break;
  243. 			default:
  244. 				break;
  245. 		}
  246. 		return parent;
  247. 	}
  248.  
  249. 	private Node joint(Node node1, Node node2)
  250. 	{
  251.  
  252. 		Node temp = null, temp2 = null, temp3 = null;
  253. 		int n;
  254.  
  255. 		Widget.Extend e = node1.widget.getExtend(node2.widget);
  256. 		switch (e)
  257. 		{
  258. 			case T_PARENT:
  259. 				{
  260. 					if (node2.pre_t_child != null)
  261. 					{
  262. 						n = node2.pre_t_child.size();
  263. 						for (int i = 0; i < n; i++)
  264. 						{
  265. 							temp2 = node2.pre_t_child.poll();
  266. 							if (node1.widget.getS() != temp2.widget.getS()
  267. 								&& node1.widget.getT() != temp2.widget.getT())
  268. 							{
  269. 								node2.pre_t_child.offer(temp2);
  270. 								continue;
  271. 							}
  272. 							temp3 = joint(node1, temp2);
  273. 							if (temp3 == null)
  274. 							{
  275. 								node2.pre_t_child.offer(temp2);
  276. 							}
  277. 							else
  278. 							{
  279. 								if (node1 != temp3)
  280. 								{
  281. 									node2.pre_t_child.offer(temp3);
  282. 									return node2;
  283. 								}
  284. 							}
  285. 						}
  286. 					}
  287. 					if (node2.t_child != null)
  288. 					{
  289. 						temp = joint(node2.t_child, node1);
  290. 						setFamily(node2, temp, Family.T_FAMILY);
  291. 					}
  292. 					else
  293. 					{
  294. 						setFamily(node2, node1, Family.T_FAMILY);
  295. 					}
  296. 					return node2;
  297. 				}
  298. 			case S_PARENT:
  299. 				{
  300. 					if (node2.pre_s_child != null)
  301. 					{
  302. 						n = node2.pre_s_child.size();
  303. 						for (int i = 0; i < n; i++)
  304. 						{
  305. 							temp2 = node2.pre_s_child.poll();
  306. 							if (node1.widget.getS() != temp2.widget.getS()
  307. 								&& node1.widget.getT() != temp2.widget.getT())
  308. 							{
  309. 								node2.pre_s_child.offer(temp2);
  310. 								continue;
  311. 							}
  312. 							temp3 = joint(node1, temp2);
  313. 							if (temp3 == null)
  314. 							{
  315. 								node2.pre_s_child.offer(temp2);
  316. 							}
  317. 							else
  318. 							{
  319. 								if (node1 != temp3)
  320. 								{
  321. 									node2.pre_s_child.offer(temp3);
  322. 									return node2;
  323. 								}
  324. 							}
  325. 						}
  326. 					}
  327. 					if (node2.s_child != null)
  328. 					{
  329. 						temp = joint(node2.s_child, node1);
  330. 						setFamily(node2, temp, Family.S_FAMILY);
  331. 					}
  332. 					else
  333. 					{
  334. 						setFamily(node2, node1, Family.S_FAMILY);
  335. 					}
  336. 					return node2;
  337. 				}
  338. 			case T_CHILD:
  339. 			case S_CHILD:
  340. 				{
  341. 					return joint(node2, node1);
  342. 				}
  343. 			case PRE_S_CHILD:
  344. 				{
  345. 					if (node1.pre_s_child != null)
  346. 					{
  347. 						n = node1.pre_s_child.size();
  348. 						for (int i = 0; i < n; i++)
  349. 						{
  350. 							temp2 = node1.pre_s_child.poll();
  351. 							if (node2.widget.getS() != temp2.widget.getS()
  352. 								&& node2.widget.getT() != temp2.widget.getT())
  353. 							{
  354. 								node1.pre_s_child.offer(temp2);
  355. 								continue;
  356. 							}
  357. 							temp3 = joint(node2, temp2);
  358. 							if (temp3 == null)
  359. 							{
  360. 								node1.pre_s_child.offer(temp2);
  361. 							}
  362. 							else
  363. 							{
  364. 								if (temp3 != node2)
  365. 								{
  366. 									node1.pre_s_child.offer(temp3);
  367. 									return node1;
  368. 								}
  369. 							}
  370. 						}
  371. 					}
  372. 					if (node1.s_child != null)
  373. 					{
  374. 						temp = joint(node1.s_child, node2);
  375. 						setFamily(node1, temp, Family.S_FAMILY);
  376. 					}
  377. 					if (temp == null)
  378. 					{
  379. 						if (node1.pre_s_child == null)
  380. 						{
  381. 							node1.pre_s_child = new ArrayDeque<Node>();
  382. 						}
  383. 						node1.pre_s_child.offer(node2);
  384. 					}
  385. 					return node1;
  386. 				}
  387. 			case PRE_T_CHILD:
  388. 				{
  389. 					if (node1.pre_t_child != null)
  390. 					{
  391. 						n = node1.pre_t_child.size();
  392. 						for (int i = 0; i < n; i++)
  393. 						{
  394. 							temp2 = node1.pre_t_child.poll();
  395. 							if (node2.widget.getS() != temp2.widget.getS()
  396. 								&& node2.widget.getT() != temp2.widget.getT())
  397. 							{
  398. 								node1.pre_t_child.offer(temp2);
  399. 								continue;
  400. 							}
  401. 							temp3 = joint(node2, temp2);
  402. 							if (temp3 == null)
  403. 							{
  404. 								node1.pre_t_child.offer(temp2);
  405. 							}
  406. 							else
  407. 							{
  408. 								if (temp3 != node2)
  409. 								{
  410. 									node1.pre_t_child.offer(temp3);
  411. 									return node1;
  412. 								}
  413. 							}
  414. 						}
  415. 					}
  416. 					if (node1.t_child != null)
  417. 					{
  418. 						temp = joint(node1.t_child, node2);
  419. 						setFamily(node1, temp, Family.T_FAMILY);
  420. 					}
  421. 					if (temp == null)
  422. 					{
  423. 						if (node1.pre_t_child == null)
  424. 						{
  425. 							node1.pre_t_child = new ArrayDeque<Node>();
  426. 						}
  427. 						node1.pre_t_child.offer(node2);
  428. 					}
  429. 					return node1;
  430. 				}
  431. 			case SAME:
  432. 				{
  433. 					return node1;
  434. 				}
  435. 			case PRE_PARENT:
  436. 			case IMPOSSIBLE:
  437. 			default:
  438. 				{
  439. 					break;
  440. 				}
  441. 		}
  442. 		return null;
  443. 	}
  444.  
  445.  
  446. 	public boolean add(Widget widget)
  447. 	{
  448. 		Node temp = joint(root, new Node(widget));
  449. 		if (temp == null)
  450. 		{
  451. 			return false;
  452. 		}
  453. 		root = temp;
  454. 		return true;
  455. 	}
  456.  
  457. 	private void calc(Node parent, Node child, int[][]array, int h, int w, boolean nocopy)
  458. 	{
  459. 		calc(child, parent.widget.getS(), parent.widget.getT(), array, h, w, nocopy);
  460. 	}
  461.  
  462.  
  463. 	private void calc(Node node, int s, int t, int[][] array, int h, int w, boolean nocopy)
  464. 	{
  465. 		if (node == null)
  466. 		{
  467. 			return;
  468. 		}
  469. 		int ds = node.widget.getS() - s;
  470. 		int dt = node.widget.getT() - t;
  471. 		int hh = h - ds;
  472. 		int ww = w - dt;
  473. 		int[][] temp;
  474. 		if (nocopy)
  475. 		{
  476. 			temp = array;
  477. 		}
  478. 		else
  479. 		{
  480. 			temp = new int[hh][ww];
  481. 		}
  482. 		int count = 0;
  483. 		for (int i = 0; i < hh; i++)
  484. 		{
  485. 			for (int j = 0; j < ww; j++)
  486. 			{
  487. 				for (int dy = 0; dy <= ds; dy++)
  488. 				{
  489. 					for (int dx = 0; dx <= dt; dx++)
  490. 					{
  491. 						temp[i][j] += array[i + dy][j + dx];
  492. 					}
  493. 				}
  494. 				if (temp[i][j] == 0)
  495. 				{
  496. 					count++;
  497. 				}
  498. 			}
  499. 		}
  500. 		node.widget.setAnswer(count);
  501. 		nocopy = node.childrenCount() < 2;
  502. 		calc(node, node.t_child, temp, hh, ww, nocopy);
  503. 		calc(node, node.s_child, temp, hh, ww, nocopy);
  504. 		if (node.pre_t_child != null)
  505. 		{
  506. 			for (Node p : node.pre_t_child)
  507. 			{
  508. 				calc(node, p, temp, hh, ww, nocopy);
  509. 			}
  510. 		}
  511. 		if (node.pre_s_child != null)
  512. 		{
  513. 			for (Node p : node.pre_s_child)
  514. 			{
  515. 				calc(node, p, temp, hh, ww, nocopy);
  516. 			}
  517. 		}
  518. 	}
  519.  
  520. 	public void calc(int h, int w, int[][] home)
  521. 	{
  522. 		calc(root, 1, 1, home, h, w, false);
  523. 	}
  524. }
  525.  
  526.  
Success #stdin #stdout 0.08s 380288KB
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/JhgpVu
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!