fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define rust(a, b, c, d) sqrt(sqr(a - c) + sqr(b - d))
  4. #define sqr(a) (a)*(a)
  5. #define m_p make_pair
  6. #define fi first
  7. #define se second
  8. #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define endl "\n"
  10. #define pll pair <ll,ll>
  11. #define next stopplz
  12. #define y1 STOPPLZ
  13.  
  14. typedef long long ll;
  15. const ll MAXN = 1e6;
  16. using namespace std;
  17. ll all = 1, a[1001], n;
  18. struct tree{
  19.     ll l, r;
  20.     long long val;
  21. };
  22. tree p[10 * MAXN];
  23.  
  24. void modify(ll v, ll ls, ll rs, ll pos, ll val){
  25.     if (ls == rs) {
  26.         p[v].val = val;
  27.         return;
  28.     }
  29.     ll mid = (ls + rs) / 2;
  30.     if (pos <= mid) {
  31.             if (p[v].l == 0) p[v].l = ++all;
  32.             modify(p[v].l, ls, mid, pos, val);
  33.     } else {
  34.             if (p[v].r == 0) p[v].r = ++all;
  35.             modify(p[v].r, mid + 1, rs, pos, val);
  36.     }
  37.  
  38.     p[v].val = p[p[v].l].val + p[p[v].r].val;
  39. }
  40.  
  41. long long get(ll v, ll ls, ll rs, ll l, ll r){
  42.     if (l > r) return 0;
  43.     if (ls == l && rs == r) return p[v].val;
  44.     ll mid = (ls + rs) / 2;
  45.     return get(p[v].l, ls, mid, l, min(r, mid)) + get(p[v].r, mid + 1, rs, max(mid + 1, l), r);
  46. }
  47.  
  48. long long getSum(ll type, ll x1, ll y1, ll x2, ll y2){
  49.     long long ans = 0;
  50.     for (int i = x1; i <= x2; ++i) {
  51. //            if (type == 1) cout << get(a[i + (type == 2 ? n : 0)], 1, n, y1, y2) << endl;
  52.             ans += get(a[i + (type == 2 ? n : 0)], 1, n, y1, y2);
  53.     }
  54.     return ans;
  55. }
  56.  
  57. void dfs(ll v1, ll v2, ll ls, ll rs, ll l, ll r, ll pred1, ll pred2, ll dir){
  58.     if (l > r) return;
  59.     if (ls == l && rs == r){
  60.         if (dir == 0) swap(p[pred1].l, p[pred2].l);
  61.         else swap(p[pred1].r, p[pred2].r);
  62.         return;
  63.     }
  64.     ll mid = (ls + rs) / 2;
  65.     dfs(p[v1].l, p[v2].l, ls, mid, l, min(r, mid), v1, v2, 0);
  66.     dfs(p[v1].r, p[v2].r, mid + 1, r, max(mid + 1, l), r, v1, v2, 1);
  67.     p[v1].val = p[p[v1].l].val + p[p[v1].r].val;
  68.     p[v2].val = p[p[v2].l].val + p[p[v2].r].val;
  69.  }
  70.  
  71. void update(ll x1, ll y1, ll x2, ll y2){
  72.     for (int i = x1; i <= x2; ++i) {
  73.             if (y1 == 1 && y2 == n){
  74.                 swap(a[i], a[i + n]);
  75.                 continue;
  76.             }
  77.             dfs(a[i], a[i + n], 1, n, y1, y2, 0, 0, 0);
  78.     }
  79.     return;
  80. }
  81. int main() {
  82.     srand(time(0));
  83. //    freopen("input.txt","r",stdin);
  84. //    freopen("output.txt","w",stdout);
  85.     fast_io;
  86.     cin >> n;
  87.     for (int i = 1; i <= 2 * n; ++i){
  88.         a[i] = all;
  89.         for (int j = 1; j <= n; ++j){
  90.             ll x;
  91.             cin >> x;
  92.             modify(a[i], 1, n, j, x);
  93.         }
  94.     }
  95.     ll q;
  96.     cin >> q;
  97.     while (q--){
  98.         ll type, x1, y1, x2, y2;
  99.         cin >> type >> x1 >> y1 >> x2 >> y2;
  100.         if (type == 0) update(x1, y1, x2, y2);
  101.         else cout << getSum(type, x1, y1, x2, y2) << endl;
  102.     }
  103.     return 0;
  104. }
  105. /*
  106. 10
  107. 8 5 2 5 6 5 5 5 5 1
  108. 0 5 7 3 2 4 6 4 4 3
  109. 1 1 5 7 6 5 9 3 7 4
  110. 4 6 9 4 5 0 8 0 9 2
  111. 2 3 6 8 0 3 1 6 4 6
  112. 7 8 9 6 5 5 3 2 4 6
  113. 5 2 3 5 7 9 4 7 3 9
  114. 9 8 8 3 6 2 7 8 1 7
  115. 0 6 7 6 0 0 3 5 8 7
  116. 7 8 0 3 6 6 2 7 7 1
  117.  
  118. 7 1 5 9 9 0 6 3 9 5
  119. 3 9 3 5 0 5 1 8 0 6
  120. 0 7 1 9 6 5 0 0 0 9
  121. 4 4 1 4 6 4 0 0 0 4
  122. 1 9 2 8 5 2 3 9 6 0
  123. 5 2 7 5 4 4 6 3 5 6
  124. 0 3 1 4 7 1 5 1 7 7
  125. 2 7 7 8 5 9 6 4 9 8
  126. 1 6 6 7 5 4 3 3 6 0
  127. 5 0 9 6 8 2 2 3 5 3
  128. 5
  129. 0 1 3 5 4
  130. 0 2 3 3 5
  131. 2 1 1 9 4
  132. 1 1 4 5 5
  133. 0 1 2 4 9
  134.  
  135.  
  136.  
  137. 168
  138. 18
  139. 5
  140. 13
  141. 10
  142. 13
  143. 59
  144.  
  145. */
  146.  
Time limit exceeded #stdin #stdout 5s 249600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZRPieT
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!