fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(ac) ac.begin(),ac.end()
  4. #define task "tet"
  5. #define fi first
  6. #define se second
  7. #define pii pair<int,int>
  8. #define db long double
  9. #define int long long
  10. #define pb push_back
  11. #define eb emplace_back
  12.  
  13. const int N = 505;
  14. int n, m, a[N][N], q;
  15. int MOD;
  16.  
  17. struct node {
  18.     int mx, mn;
  19.     node(int mx = -1e18, int mn = 1e18): mx(mx), mn(mn) {}
  20. };
  21.  
  22. struct segtree {
  23.     int n;
  24.     vector <node> tree;
  25.  
  26.     segtree(int n): n(n), tree(n << 2 | 1, node()) {}
  27.  
  28.     node Merge(node a, node b) {
  29.         node res;
  30.         res.mx = max(a.mx, b.mx);
  31.         res.mn = min(a.mn, b.mn);
  32.         return res;
  33.     }
  34.  
  35.     void update(int id, int l, int r, int pos, int w) {
  36.         if(l > pos || r < pos) return;
  37.         if(l == r) {
  38.             if(w == -1) tree[id] = node();
  39.             else {
  40.                 tree[id].mx = w;
  41.                 tree[id].mn = w;
  42.             }
  43.             return;
  44.         }
  45.  
  46.         int mid = (l + r) >> 1;
  47.         update(id << 1, l, mid, pos, w);
  48.         update(id << 1 | 1, mid + 1, r, pos, w);
  49.         tree[id] = Merge(tree[id << 1], tree[id << 1 | 1]);
  50.         return;
  51.     }
  52.  
  53.     int get(int id, int l, int r, int u, int v, int x, int y) {
  54.         if(l > v || r < u || tree[id].mn >= x && tree[id].mx <= y) return MOD;
  55.         if(l == r) return l;
  56.  
  57.         int mid = (l + r) >> 1;
  58.         if(l >= u && r <= v) {
  59.             node val_left = tree[id << 1];
  60.             if(val_left.mx > y || val_left.mn < x)
  61.                 return get(id << 1, l, mid, u, v, x, y);
  62.             return get(id << 1 | 1, mid + 1, r, u, v, x, y);
  63.         }
  64.         return min(get(id << 1 | 1, mid + 1, r, u, v, x, y), get(id << 1, l, mid, u, v, x, y));
  65.     }
  66.  
  67.     void update(int pos, int w) {
  68.         return update(1, 0, n - 1, pos, w), void();
  69.     }
  70.  
  71.     int get(int l, int r, int x, int y) {
  72.         return get(1, 0, n - 1, l, r, x, y);
  73.     }
  74. };
  75.  
  76. int32_t main() {
  77.     if(fopen(task".inp", "r")) {
  78.         freopen(task".inp", "r", stdin);
  79.         freopen(task".out", "w", stdout);
  80.     }
  81.  
  82.     ios::sync_with_stdio(false);
  83.     cin.tie(0), cout.tie(0);
  84.  
  85.     cin >> n >> m;
  86.     MOD = n * m;
  87.     segtree Col(MOD), Row(MOD);
  88.     for(int i=1;i<=n;i++) {
  89.         for(int j=1;j<=m;j++) {
  90.             cin >> a[i][j];
  91.             Row.update(a[i][j], i);
  92.             Col.update(a[i][j], j);
  93.         }
  94.     }
  95.  
  96.     cin >> q;
  97.     int w = 0;
  98.     while(q--) {
  99.         int type; cin >> type;
  100.         if(type == 1) {
  101.             int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
  102.             Row.update(a[r1][c1], r2);
  103.             Row.update(a[r2][c2], r1);
  104.             Col.update(a[r1][c1], c2);
  105.             Col.update(a[r2][c2], c1);
  106.             swap(a[r1][c1], a[r2][c2]);
  107.         }
  108.         else
  109.         if(type == 2) {
  110.             int ww; cin >> ww;
  111.             w = (w + ww) % MOD;
  112.         }
  113.         else {
  114.             int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
  115.             if(r1 == 1 && c1 == 1 && r2 == n && c2 == m) {
  116.                 cout << "-1\n";
  117.                 continue;
  118.             }
  119.  
  120.             int ans = min(Col.get(MOD - w, MOD - 1, c1, c2), Row.get(MOD - w, MOD - 1, r1, r2));
  121.             if(ans != MOD) {
  122.                 cout << ans - MOD + w << '\n';
  123.                 continue;
  124.             }
  125.             cout << min(Row.get(0, MOD - w - 1, r1, r2), Col.get(0, MOD - w - 1, c1, c2)) + w << '\n';
  126.         }
  127.     }
  128.     return 0;
  129. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TcVCS4
language:
C++14 (gcc 8.3)
created:
7 days 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!