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.     node get(int id, int l, int r, int u, int v) {
  54.         if(l > v || r < u) return node();
  55.         if(l >= u && r <= v) return tree[id];
  56.  
  57.         int mid = (l + r) >> 1;
  58.         return Merge(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
  59.     }
  60.  
  61.     void update(int pos, int w) {
  62.         return update(1, 0, n - 1, pos, w), void();
  63.     }
  64.  
  65.     node get(int l, int r) {
  66.         return get(1, 0, n - 1, l, r);
  67.     }
  68. } Row(N * N), Col(N * N);
  69.  
  70. int32_t main() {
  71.     if(fopen(task".inp", "r")) {
  72.         freopen(task".inp", "r", stdin);
  73.         freopen(task".out", "w", stdout);
  74.     }
  75.  
  76.     ios::sync_with_stdio(false);
  77.     cin.tie(0), cout.tie(0);
  78.  
  79.     cin >> n >> m;
  80.     for(int i=1;i<=n;i++) {
  81.         for(int j=1;j<=m;j++) {
  82.             cin >> a[i][j];
  83.             Row.update(a[i][j], i);
  84.             Col.update(a[i][j], j);
  85.         }
  86.     }
  87.     MOD = n * m;
  88.  
  89.     cin >> q;
  90.     int w = 0;
  91.     while(q--) {
  92.         int type; cin >> type;
  93.         if(type == 1) {
  94.             int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
  95.             Row.update(a[r1][c1], r2);
  96.             Row.update(a[r2][c2], r1);
  97.             Col.update(a[r1][c1], c2);
  98.             Col.update(a[r2][c2], c1);
  99.             swap(a[r1][c1], a[r2][c2]);
  100.         }
  101.         else
  102.         if(type == 2) {
  103.             int ww; cin >> ww;
  104.             w = (w + ww) % MOD;
  105.         }
  106.         else {
  107.             int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
  108.             if(r1 == 1 && c1 == 1 && r2 == n && c2 == m) {
  109.                 cout << "-1\n";
  110.                 continue;
  111.             }
  112.  
  113.             int ans = -1;
  114.             if(w != 0) {
  115.                 int p = MOD - w;
  116.                 int lo = 0, hi = w - 1;
  117.                 while(lo <= hi) {
  118.                     int mid = (lo + hi) >> 1;
  119.                     node val_row = Row.get(p, p + mid);
  120.                     node val_col = Col.get(p, p + mid);
  121.                     if(val_row.mx > r2 || val_row.mn < r1 || val_col.mx > c2 || val_col.mn < c1) {
  122.                         ans = mid;
  123.                         hi = mid - 1;
  124.                     }
  125.                     else lo = mid + 1;
  126.                 }
  127.             }
  128.             if(ans != -1) {
  129.                 cout << ans << '\n';
  130.                 continue;
  131.             }
  132.             int lo = w, hi = MOD - 1;
  133.             while(lo <= hi) {
  134.                 int mid = (lo + hi) >> 1;
  135.                 node val_row = Row.get(0, mid - w);
  136.                 node val_col = Col.get(0, mid - w);
  137.                 if(val_row.mx > r2 || val_row.mn < r1 || val_col.mx > c2 || val_col.mn < c1) {
  138.                     ans = mid;
  139.                     hi = mid - 1;
  140.                 }
  141.                 else lo = mid + 1;
  142.             }
  143.             cout << ans << '\n';
  144.         }
  145.     }
  146.     return 0;
  147. }
Success #stdin #stdout 0.01s 34876KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/U8jKXq
language:
C++14 (gcc 8.3)
created:
12 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!