fork(1) download 
  1. # paiza POH! vol.2
  2. # result:
  3. # http://p...content-available-to-author-only...a.jp/poh/paizen/result/4718ef77205c2f35c3de7437ae514358
  4. # author: Leonardone @ NEETSDKASU
  5. h, w = map(int, raw_input().split())
  6. sp = [[0 for j in range(w)] for i in range(h)]
  7. for y in range(h) :
  8. 	str = raw_input()
  9. 	c = 0
  10. 	for x in range(w) :
  11. 		if str[x] == '0' :
  12. 			c = c + 1
  13. 		else :
  14. 			c = 0
  15. 		sp[y][x] = c
  16. tb = [[0 for j in range(w + 1)] for i in range(h + 1)]
  17. ca = [[0 for j in range(w + 1)] for i in range(h + 1)]
  18. for y in range(h) :
  19. 	for x in range(w) :
  20. 		if sp[y][x] == 0 :
  21. 			continue
  22. 		s, t = 1, sp[y][x]
  23. 		for i in range(y, h) :
  24. 			if sp[i][x] == 0 :
  25. 				break
  26. 			t = min(sp[i][x], t)
  27. 			tb[s][t] = tb[s][t] + 1
  28. 			s = s + 1
  29.  
  30. n = int(raw_input())
  31. for i in range(n) :
  32. 	s, t = map(int, raw_input().split())
  33. 	if s > h or t > w :
  34. 		print "0"
  35. 	else :
  36. 		if ca[s][t] > 0 :
  37. 			print ca[s][t] - 1
  38. 		else :
  39. 			c = 0
  40. 			for j in range(t, w + 1) :
  41. 				c = c + tb[s][j]
  42. 			ca[s][t] = c + 1
  43. 			print c
  44.  
Success #stdin #stdout 0.01s 7856KB
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/lnM6eC
language:
Python (cpython 2.7.16)
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!