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