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