fork(30) download 
  1. // Domino (C), by Errichto
  2. // AC, O(wh + q)
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. const int nax = 2005;
  7. char sl[nax][nax];
  8. // horizontal and vertical
  9. int hor[nax][nax], ver[nax][nax];
  10.  
  11. int main() {
  12. 	int w, h;
  13. 	scanf("%d%d", &h, &w);
  14. 	for(int y = 0; y < h; ++y) scanf("%s", sl[y]);
  15. 	for(int y = 0; y < h; ++y) for(int x = 0; x < w; ++x) {
  16. 		hor[x+1][y+1] = hor[x][y+1] + hor[x+1][y] - hor[x][y];
  17. 		ver[x+1][y+1] = ver[x][y+1] + ver[x+1][y] - ver[x][y];
  18. 		if(sl[y][x] != '.') continue;
  19. 		if(x != w - 1 && sl[y][x+1] == '.') ++hor[x+1][y+1];
  20. 		if(y != h - 1 && sl[y+1][x] == '.') ++ver[x+1][y+1];
  21. 	}
  22. 	int q;
  23. 	scanf("%d", &q);
  24. 	while(q--) {
  25. 		int x1, y1, x2, y2;
  26. 		scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
  27. 		--x1;--y1;
  28. 		int ans = 0;
  29. 		ans += hor[x2-1][y2] - hor[x1][y2] - hor[x2-1][y1] + hor[x1][y1];
  30. 		ans += ver[x2][y2-1] - ver[x1][y2-1] - ver[x2][y1] + ver[x1][y1];
  31. 		printf("%d\n", ans);
  32. 	}
  33. 	return 0;
  34. }
Time limit exceeded #stdin #stdout 5s 38792KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/wHsZej
Domino
language:
C++14 (gcc 8.3)
created:
8 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!