ProgMe

Untitled

Nov 28th, 2020
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <bits/extc++.h>
  3.  
  4. #define int int64_t
  5.  
  6. #pragma GGG optimize("O3")
  7.  
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10.  
  11. template<typename T>
  12. using orset = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  13. template<typename T, typename K>
  14. using ormap = tree <T, K, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  15.  
  16. const int N = 500;
  17.  
  18. int n, m, q;
  19. int a[N][N];
  20.  
  21. int get(int fx, int fy, int sx, int sy){
  22. int sum = a[sx][sy];
  23. if (fx > 0)
  24. sum -= a[fx - 1][sy];
  25. if (fy > 0)
  26. sum -= a[sx][fy - 1];
  27. if (fy > 0 && fx > 0)
  28. sum += a[fx -1][fy - 1];
  29. return sum;
  30. }
  31.  
  32. int32_t main() {
  33. ios::sync_with_stdio(false);
  34. cin >> n >> m>> q;
  35. for(int i = 0; i < n; i++){
  36. for(int j = 0; j < m; j++){
  37. cin >> a[i][j];
  38. }
  39. }
  40. for(int i = 1; i < n; i++)
  41. a[i][0] += a[i - 1][0];
  42. for(int i = 1; i < m; i++)
  43. a[0][i] += a[0][i - 1];
  44. for(int i = 1; i < n; i++){
  45. for(int j = 1; j < m; j++)
  46. a[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
  47. }
  48. while(q--){
  49. int fi, fj, si, sj;
  50. cin >> fi >> fj >> si >> sj;
  51. fi--, si--, fj--, sj--;
  52. cout << get(fi, fj, si, sj) << " ";
  53. }
  54. }
  55.  
Advertisement
Add Comment
Please, Sign In to add comment