ProgMe

Untitled

Nov 28th, 2020
175
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.34 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. int n, m, q;
  17. vector<vector<int>> a;
  18.  
  19. int get(int fx, int fy, int sx, int sy){
  20. int sum = a[sx][sy];
  21. if (fx > 0)
  22. sum -= a[fx - 1][sy];
  23. if (fy > 0)
  24. sum -= a[sx][fy - 1];
  25. if (fy > 0 && fx > 0)
  26. sum += a[fx -1][fy - 1];
  27. return sum;
  28. }
  29.  
  30. int32_t main() {
  31. ios::sync_with_stdio(false);
  32. cin >> n >> m>> q;
  33. a.resize(n);
  34. for(int i = 0; i < n; i++){
  35. a[i].resize(m);
  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. }
Advertisement
Add Comment
Please, Sign In to add comment