fork(1) download
  1. /*
  2.   author: kartik8800
  3. */
  4. #include<bits/stdc++.h>
  5. #define ll long long
  6. #define pb push_back
  7. #define fr(a,b) for(ll i = a; i < b; i++)
  8. #define mod 1000000007
  9. #define inf (1LL<<60)
  10. #define all(x) (x).begin(), (x).end()
  11. #define prDouble(x) cout << fixed << setprecision(10) << x
  12. #define triplet pair<ll,pair<ll,ll>>
  13. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  14. using namespace std;
  15.  
  16. bool grid[1001][1001];
  17. int dp[1001][1001];
  18.  
  19. void build_dp(int n, int m)
  20. {
  21. dp[0][0] = dp[1][0] = dp[0][1] = 0;
  22.  
  23. for(int i = 1; i <= n; i++)
  24. {
  25. for(int j = 1; j <= n; j++)
  26. dp[i][j] = grid[i][j] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1];
  27. }
  28. }
  29.  
  30. int getDP(int x, int y)
  31. {
  32. return dp[x][y];
  33. }
  34.  
  35. int query(int x1, int y1, int x2, int y2)
  36. {
  37. return getDP(x2,y2) - getDP(x2,y1-1) - getDP(x1-1,y2) + getDP(x1-1,y1-1);
  38. }
  39.  
  40. int main() {
  41. fast_io;
  42. int n,q;
  43. cin >> n >> q;
  44.  
  45. for(int i = 1; i <= n; i++)
  46. {
  47. for(int j = 1; j <= n; j++)
  48. {
  49. char ch;
  50. cin >> ch;
  51. if(ch == '*')
  52. grid[i][j] = 1;
  53. else grid[i][j] = 0;
  54. }
  55. }
  56.  
  57. build_dp(n,n);
  58.  
  59. while(q--)
  60. {
  61. int x1,x2,y1,y2;
  62. cin >> x1 >> y1 >> x2 >> y2;
  63. cout << query(x1,y1,x2,y2) << '\n';
  64. }
  65. return 0;
  66. }
  67.  
Success #stdin #stdout 0s 4160KB
stdin
4 3
.*..
*.**
**..
****
2 2 3 4
3 1 3 1
1 1 2 2
stdout
3
1
2