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