API tools faq
paste
prog3r

damn

prog3r
Jul 14th, 2025
130
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.00 KB | None | 0 0
raw download clone embed print report
  1. //#include <bits/extc++.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. //using namespace __gnu_pbds;
  5. //template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  6. #define int long long
  7. //#define double long double
  8. #define YES(x) cout << (x?"YES\n":"NO\n")
  9. #define ALICE(x) cout << (x?"Alice\n":"Bob\n")
  10. #define BOB(x) cout << (x?"Bob\n":"Alice\n")
  11. #define NO(x) cout << (x?"NO\n":"YES\n")
  12. #ifdef LO
  13. #pragma GCC optimize("trapv")
  14. #endif
  15. #ifndef LO
  16. #pragma GCC optimize("Ofast,unroll-loops")
  17. #endif
  18. //constexpr int MOD = (119<<23)+1;
  19. //constexpr int MOD = 967276608647009887ll;
  20. //constexpr int MOD = 1e9+7;
  21. //constexpr int INF = 1e18;
  22. signed main() {
  23.     int T;
  24.     cin >> T;
  25.     for (int tt = 0; tt < T; tt += 1) {
  26.         int n, m;
  27.         cin >> n >> m;
  28.         vector<vector<int>> a(n, vector<int>(m));
  29.         for (auto &x : a) {
  30.             for (auto &y : x) {
  31.                 cin >> y;
  32.             }
  33.         }
  34.         int q;
  35.         cin >> q;
  36.         // [к какой стенке][куда идет треугольник ч1 (нлвп)][куда идет треугольник ч2: += по той коорде которая меняется или -= ]
  37.         vector<vector<vector<vector<vector<int>>>>> SU(4, vector<vector<vector<vector<int>>>>(4, vector<vector<vector<int>>>(2, vector<vector<int>>(n, vector<int>(m)))));
  38.         vector<vector<vector<vector<vector<int>>>>> SU_A(4, vector<vector<vector<vector<int>>>>(4, vector<vector<vector<int>>>(2, vector<vector<int>>(n, vector<int>(m)))));
  39.         vector<vector<vector<int>>> R(4, vector<vector<int>>(n, vector<int>(m)));
  40.         vector<vector<vector<int>>> R_A(4, vector<vector<int>>(n, vector<int>(m)));
  41.         auto val = [&] (int type, int i, int j) -> int {
  42.             if (type == 0) {
  43.                 return n-i;
  44.             }
  45.             if (type == 1) {
  46.                 return j+1;
  47.             }
  48.             if (type == 2) {
  49.                 return i+1;
  50.             }
  51.             if (type == 3) {
  52.                 return m-j;
  53.             }
  54.             assert(false);
  55.         };
  56.         for (int k = 0; k < 4; k += 1) {
  57.             for (int i = 0; i < n; i += 1) {
  58.                 for (int j = 0; j < m; j += 1) {
  59.                     R[k][i][j] = val(k, i, j)*a[i][j];
  60.                     R_A[k][i][j] = a[i][j];
  61.                     if (i) {
  62.                         R[k][i][j] += R[k][i-1][j];
  63.                         R_A[k][i][j] += R_A[k][i-1][j];
  64.                     }
  65.                     if (j) {
  66.                         R[k][i][j] += R[k][i][j-1];
  67.                         R_A[k][i][j] += R_A[k][i][j-1];
  68.                     }
  69.                     if (i && j) {
  70.                         R[k][i][j] -= R[k][i-1][j-1];
  71.                         R_A[k][i][j] -= R_A[k][i-1][j-1];
  72.                     }
  73.                 }
  74.             }
  75.         }
  76.         auto rect_sum = [&] (const vector<vector<int>>& v, int lr, int lc, int rr, int rc) -> int {
  77.             lr = max(lr, 0ll);
  78.             lc = max(lc, 0ll);
  79.             rr = min(rr, n-1);
  80.             rc = min(rc, m-1);
  81.             if (lr > rr || lc > rc) {
  82.                 return 0;
  83.             }
  84.             int ans = v[rr][rc];
  85.             ans -= lc?v[rr][lc-1]:0;
  86.             ans -= lr?v[lr-1][rc]:0;
  87.             ans += lc&&lr?v[lr-1][lc-1]:0;
  88.             return ans;
  89.         };
  90.         auto valid = [&] (int i, int j) -> bool {
  91.             return i>=0&&i<n&&j>=0&&j<m;
  92.         };
  93.         for (int k = 0; k < 4; k += 1) {
  94.             for (int i = n-1; i >= 0; i -= 1) {
  95.                 for (int j = 0; j < m; j += 1) {
  96.                     SU[k][0][0][i][j] = SU[k][0][1][i][j] = rect_sum(R[k], i, j, n-1, j);
  97.                     SU_A[k][0][0][i][j] = SU_A[k][0][1][i][j] = rect_sum(R_A[k], i, j, n-1, j);
  98.                     if (valid(i+1, j+1)) {
  99.                         SU[k][0][1][i][j] += SU[k][0][1][i+1][j+1];
  100.                         SU_A[k][0][1][i][j] += SU_A[k][0][1][i+1][j+1];
  101.                     }
  102.                     if (valid(i+1, j-1)) {
  103.                         SU[k][0][0][i][j] += SU[k][0][0][i+1][j-1];
  104.                         SU_A[k][0][0][i][j] += SU_A[k][0][0][i+1][j-1];
  105.                     }
  106.                 }
  107.             }
  108.             for (int i = 0; i < n; i += 1) {
  109.                 for (int j = 0; j < m; j += 1) {
  110.                     SU[k][2][0][i][j] = SU[k][2][1][i][j] = rect_sum(R[k], 0, j, i, j);
  111.                     SU_A[k][2][0][i][j] = SU_A[k][2][1][i][j] = rect_sum(R_A[k], 0, j, i, j);
  112.                     if (valid(i-1, j+1)) {
  113.                         SU[k][2][1][i][j] += SU[k][2][1][i-1][j+1];
  114.                         SU_A[k][2][1][i][j] += SU_A[k][2][1][i-1][j+1];
  115.                     }
  116.                     if (valid(i-1, j-1)) {
  117.                         SU[k][2][0][i][j] += SU[k][2][0][i-1][j-1];
  118.                         SU_A[k][2][0][i][j] += SU_A[k][2][0][i-1][j-1];
  119.                     }
  120.                 }
  121.             }
  122.             for (int j = 0; j < m; j += 1) {
  123.                 for (int i = 0; i < n; i += 1) {
  124.                     SU[k][1][0][i][j] = SU[k][1][1][i][j] = rect_sum(R[k], i, 0, i, j);
  125.                     SU_A[k][1][0][i][j] = SU_A[k][1][1][i][j] = rect_sum(R_A[k], i, 0, i, j);
  126.                     if (valid(i+1, j-1)) {
  127.                         SU[k][1][1][i][j] += SU[k][1][1][i+1][j-1];
  128.                         SU_A[k][1][1][i][j] += SU_A[k][1][1][i+1][j-1];
  129.                     }
  130.                     if (valid(i-1, j-1)) {
  131.                         SU[k][1][0][i][j] += SU[k][1][0][i-1][j-1];
  132.                         SU_A[k][1][0][i][j] += SU_A[k][1][0][i-1][j-1];
  133.                     }
  134.                 }
  135.             }
  136.             for (int j = m-1; j >= 0; j -= 1) {
  137.                 for (int i = 0; i < n; i += 1) {
  138.                     SU[k][3][0][i][j] = SU[k][3][1][i][j] = rect_sum(R[k], i, j, i, n-1);
  139.                     SU_A[k][3][0][i][j] = SU_A[k][3][1][i][j] = rect_sum(R_A[k], i, j, i, n-1);
  140.                     if (valid(i+1, j+1)) {
  141.                         SU[k][3][1][i][j] += SU[k][3][1][i+1][j+1];
  142.                         SU_A[k][3][1][i][j] += SU_A[k][3][1][i+1][j+1];
  143.                     }
  144.                     if (valid(i-1, j+1)) {
  145.                         SU[k][3][0][i][j] += SU[k][3][0][i-1][j+1];
  146.                         SU_A[k][3][0][i][j] += SU_A[k][3][0][i-1][j+1];
  147.                     }
  148.                 }
  149.             }
  150.         }
  151.         // 0 = down, 1 = left, 2 = up, 3 = right
  152.         vector<function<int(int, int, int, int, const vector<vector<int>>, const vector<vector<int>>&)>> f = {
  153.         [&] (int r, int c, int end, int mnozh, const vector<vector<int>>& s, const vector<vector<int>>& rect) -> int {
  154.             return s[r][c] - (valid(end+1, c+(end-r)*mnozh+mnozh)?s[end+1][c+(end-r)*mnozh+mnozh]:0) - (mnozh==-1?rect_sum(rect, end+1, c+(end-r)*mnozh, n-1, c):rect_sum(rect, end+1, c, n-1, c+(end-r)*mnozh));
  155.         },
  156.         [&] (int r, int c, int end, int mnozh, const vector<vector<int>>& s, const vector<vector<int>>& rect) -> int {
  157.             return s[r][c] - (valid(r+(c-end)*mnozh+mnozh, end-1)?s[r+(c-end)*mnozh+mnozh][end-1]:0) - (mnozh==-1?rect_sum(rect, r+(c-end)*mnozh, 0, r, end-1):rect_sum(rect, r, 0, r+(c-end)*mnozh, end-1));
  158.         },
  159.         [&] (int r, int c, int end, int mnozh, const vector<vector<int>>& s, const vector<vector<int>>& rect) -> int {
  160.             return s[r][c] - (valid(end-1, c+(r-end)*mnozh+mnozh)?s[end-1][c+(r-end)*mnozh+mnozh]:0) - (mnozh==-1?rect_sum(rect, 0, c+(r-end)*mnozh, end-1, c):rect_sum(rect, 0, c, end-1, c+(r-end)*mnozh));
  161.         },
  162.         [&] (int r, int c, int end, int mnozh, const vector<vector<int>>& s, const vector<vector<int>>& rect) -> int {
  163.             return s[r][c] - (valid(r+(end-c)*mnozh+mnozh, end+1)?s[r+(end-c)*mnozh+mnozh][end+1]:0) - (mnozh==-1?rect_sum(rect, r+(end-c)*mnozh, end+1, r, n-1):rect_sum(rect, r, end+1, r+(end-c)*mnozh, m-1));
  164.         }
  165.         };
  166.         auto treug = [&] (int r, int c, int end, int i, int j, int k) -> int {
  167.             int mnozh = k?1:-1;
  168.             int cancel=i==0?n-1-r:i==3?m-1-c:i==2?r:c;
  169.             return f[j](r, c, end, mnozh, SU[i][j][k], R[i]) - f[j](r, c, end, mnozh, SU_A[i][j][k], R_A[i])*cancel;
  170.         };
  171.         for (int ii = 0; ii < q; ii += 1) {
  172.             int lr, lc, rr, rc;
  173.             cin >> lr >> lc >> rr >> rc;
  174.             lr -= 1, rr -= 1, lc -= 1, rc -= 1;
  175.             int w = rc - lc + 1;
  176.             int h = rr - lr + 1;
  177.             if (h <= w) {
  178.                 int levo = (h>2?treug(rr-1, lc, rr-min(w/2, h/2)+(min(h, w)%2==0), 1, 2, 1):0) + (h>3?treug(lr+1, lc, lr+min(w/2, h/2)-1, 1, 0, 1):0);
  179.                 int pravo = (h>2?treug(rr-1, rc, rr-min(w/2, h/2)+(min(h, w)%2==0), 3, 2, 0):0) + (h>3?treug(lr+1, rc, lr+min(w/2, h/2)-1, 3, 0, 0):0);
  180. //                cout << levo << " " << pravo << " ";
  181.                 int niz = treug(rr, rc, rc+1-min(w/2, h/2), 0, 1, 0) + treug(rr, lc, lc-1+min(w/2, h/2), 0, 3, 0);
  182.                 niz += rect_sum(R[0], lr+min(w/2, h/2), lc+min(w/2, h/2), rr, rc-min(w/2, h/2))-rect_sum(R_A[0], lr+min(w/2, h/2), lc+min(w/2, h/2), rr, rc-min(w/2, h/2))*(n-1-rr);
  183. //                cout << niz << " ";
  184.                 int ans = levo+pravo+niz;
  185.                 if (h > 1) {
  186.                     int verh = treug(lr, lc, lc-1+min(w/2, h/2), 2, 3, 1) + treug(lr, rc, rc+1-min(w/2, h/2), 2, 1, 1);
  187.                     verh += rect_sum(R[2], lr, lc+min(w/2, h/2), lr+min(w/2, h/2)-1, rc-min(w/2, h/2)) - rect_sum(R_A[2], lr, lc+min(w/2, h/2), lr+min(w/2, h/2)-1, rc-min(w/2, h/2))*(lr);
  188. //                    cout << verh << " ";
  189.                     ans += verh;
  190.                 }
  191.                 cout << ans << "\n";
  192. //                cout << "\n";
  193.             } else {
  194.                 int niz = (w>2?treug(rr, rc-1, rc-min(w/2, h/2)+(min(h, w)%2==0), 0, 1, 0):0) + (w>3?treug(rr, lc+1, lc+min(w/2, h/2)-1, 0, 3, 0):0);
  195.                 int verh = (w>2?treug(lr, lc+1, lc+min(w/2, h/2)-(min(h, w)%2==0), 2, 3, 1):0) + (w>3?treug(lr, rc-1, rc-min(w/2, h/2)+1, 2, 1, 1):0);
  196. //                cout << niz << " " << verh << " ";
  197.                 int levo = treug(rr, lc, rr+1-min(w/2, h/2), 1, 2, 1) + treug(lr, lc, lr-1+min(w/2, h/2), 1, 0, 1);
  198.                 levo += rect_sum(R[1], lr+min(w/2, h/2), lc, rr-min(w/2, h/2), rc-min(w/2, h/2))-rect_sum(R_A[1], lr+min(w/2, h/2), lc, rr-min(w/2, h/2), rc-min(w/2, h/2))*(lc);
  199. //                cout << levo << " ";
  200.                 int ans = niz+verh+levo;
  201.                 if (w > 1) {
  202.                     int pravo = treug(rr, rc, rr+1-min(w/2, h/2), 3, 2, 0) + treug(lr, rc, lr-1+min(w/2, h/2), 3, 0, 0);
  203. //                    clog << "(" << pravo << ")\n";
  204.                     pravo += rect_sum(R[3], lr+min(w/2, h/2), rc-min(w/2, h/2)+1, rr-min(w/2, h/2), rc)-rect_sum(R_A[3], lr+min(w/2, h/2), rc-min(w/2, h/2)+1, rr-min(w/2, h/2), rc)*(m-1-rc);
  205. //                    cout << pravo << " ";
  206.                     ans += pravo;
  207.                 }
  208.                 cout << ans << "\n";
  209. //                cout << "\n";
  210.             }
  211.         }
  212.     }
  213. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!