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
stdin
Standard input is empty
stdout
Standard output is empty