fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //#define int long long;
  4. #define fi first
  5. #define se second
  6. #define pii pair <int, int> 
  7. #define rect pair<pii, pii>
  8. const int MAXN = 5e2 +5;
  9. int n, m, q, a[MAXN][MAXN], r1,r2, y, y2, w, p, t;
  10. rect st[4*MAXN*MAXN];
  11.  
  12. rect join(rect a, rect b){
  13.     a.fi.fi = min(a.fi.fi, b.fi.fi);
  14.      a.fi.se = max(a.fi.se, b.fi.se);
  15.       a.se.fi = min(a.se.fi, b.se.fi);
  16.        a.se.se = max(a.se.se, b.se.se);
  17.  
  18.        return a;
  19. }
  20.  
  21. void update(int id, int l , int r, int x, rect pos){
  22.     if(l==r){
  23.         st[id] = pos;
  24.         return;
  25.     }
  26.  
  27.     int mid = (l+r)/2;
  28.     if(x <= mid) update(id*2, l, mid, x, pos);
  29.     else update(id*2+1, mid+1, r, x, pos);
  30.     st[id] = join(st[id*2], st[id*2+1]);
  31. }
  32.  
  33. rect query(int id, int l, int r, int x, int y){
  34.     if ( l > y || r < x){
  35.         return {{n,1},{m,1}};
  36.     }
  37.     if ( x <= l && r <= y){
  38.         return st[id];
  39.     }
  40.     int mid=(l+r)/2;
  41.     return join(query(id*2, l, mid, x, y), query(id*2+1, mid+1, r, x, y));
  42. }
  43.  
  44. signed main(){
  45.     cin >> n >> m;
  46.     for (int i =1; i <= n; i++){
  47.         for (int j =1; j <= m ; j++){
  48.             cin >> a[i][j];
  49.             update(1, 0, n*m-1, a[i][j], {{i,i}, {j,j}});
  50.         }
  51.     }
  52.     cin >> q;
  53.     while(q--){
  54.         cin >> t;
  55.         if(t==1){
  56.             cin >> r1 >> y >> r2 >> y2;
  57.             swap(a[r1][y], a[r2][y2]);
  58.             update(1, 0, n*m-1, a[r1][y], {{r1, r1}, {y, y}});
  59.             update(1, 0, n*m-1, a[r2][y2], {{r2, r2}, {y2, y2}});
  60.                  continue;
  61.         }
  62.         else if (t ==2){
  63.             cin >> w;
  64.             p = (p+w)%(n*m);
  65.         }
  66.         else{
  67.             cin >> r1 >> y >> r2 >> y2;
  68.             int l = (n*m)-p, r = n*m-1, res =-1;
  69.             rect x = query(1, 0, n*m-1, l, r);
  70.             if ( r1 <= x.fi.fi && x.fi.se <= r2 && y <= x.se.fi && x.se.se <= y2){
  71.                 r = l-1;
  72.                 l=0;
  73.             }
  74.  
  75.             while(l <= r){
  76.                 int mid = (l+r)/2;
  77.                 x = query(1, 0, n*m-1, l, mid);
  78.                  if ( r1 <= x.fi.fi && x.fi.se <= r2 && y <= x.se.fi && x.se.se <= y2){
  79.              l = mid+1;
  80.             }
  81.             else{
  82.                 res = mid;
  83.                 r = mid-1;
  84.  
  85.             }
  86.             }
  87.             if (res==-1){
  88.                 cout << res << endl;
  89.             }
  90.             else{
  91.                 cout << (res+p) % (n*m) << endl;
  92.             }
  93.             }
  94.         }
  95.  
  96.     }
  97.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4 3
11 10 9
2 6 7
1 5 0
3 8 4
6
3 2 1 3 3
1 2 3 1 2
2 7
3 1 2 4 2
3 1 1 4 3
3 4 1 4 1
stdout
copy 
3
4
-1
0
https://ideone.com/qnPbAt
language:
C++ (gcc 8.3)
created:
4 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!