#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int N=1<<20;
int lst[N], dodaj[2*N], dx[]={1, 0, -1, 0, 0}, dy[]={0, 1, 0, -1, 0}, MA;
pair<int,int>tr[2*N], gdzie[N];
vector<vector<int>>T;
void licz(int v) {
if(tr[2*v].st<tr[2*v+1].st) tr[v]=tr[2*v];
else if(tr[2*v].st>tr[2*v+1].st) tr[v]=tr[2*v+1];
else tr[v]={tr[2*v].st, tr[2*v].nd+tr[2*v+1].nd};
}
void spl(int v) {
tr[2*v].st+=dodaj[v];
tr[2*v+1].st+=dodaj[v];
dodaj[2*v]+=dodaj[v];
dodaj[2*v+1]+=dodaj[v];
dodaj[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
if(b<l || a>r) return;
if(a<=l && r<=b) {
tr[v].st+=x;
dodaj[v]+=x;
return;
}
if(dodaj[v]) spl(v);
int mid=(l+r)/2;
upd(2*v, l, mid, a, b, x);
upd(2*v+1, mid+1, r, a, b, x);
licz(v);
}
void cnt(int x, int y, int k) {
if(T[x][y]==MA) return;
if(lst[T[x][y]]==k) return;
lst[T[x][y]]=k;
rep(i, 4) {
int a=min(T[x+dx[i]][y+dy[i]], T[x+dx[(i+1)%4]][y+dy[(i+1)%4]])-1;
int b=max(T[x+dx[i]][y+dy[i]], T[x+dx[(i+1)%4]][y+dy[(i+1)%4]]);
if(T[x][y]<=a) upd(1, 0, N-1, T[x][y], a, k);
if(b<T[x][y]) upd(1, 0, N-1, b, T[x][y]-1, 10*k);
}
}
void give_initial_chart(int H, int W, vector<int>R, vector<int>C) {
MA=H*W;
rep(i, H+2) {
vector<int>P(W+2, H*W);
T.pb(P);
}
rep(i, H*W) {
T[R[i]+1][C[i]+1]=i;
gdzie[i]={R[i]+1, C[i]+1};
}
rep(i, N) tr[N+i]={N, 0};
rep(i, H*W) tr[N+i]={0, 1};
for(int i=N-1; i; --i) licz(i);
rep(i, H) rep(j, W) cnt(i+1, j+1, 1);
}
int swap_seats(int a, int b) {
rep(i, 5) {
int x=gdzie[a].st+dx[i], y=gdzie[a].nd+dy[i];
cnt(x, y, -1);
x=gdzie[b].st+dx[i]; y=gdzie[b].nd+dy[i];
cnt(x, y, -1);
}
swap(T[gdzie[a].st][gdzie[a].nd], T[gdzie[b].st][gdzie[b].nd]);
swap(gdzie[a], gdzie[b]);
rep(i, 5) {
int x=gdzie[a].st+dx[i], y=gdzie[a].nd+dy[i];
cnt(x, y, 1);
x=gdzie[b].st+dx[i]; y=gdzie[b].nd+dy[i];
cnt(x, y, 1);
}
return tr[1].nd;
}
