#include "seats.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int nmax=1000*1000+5;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
struct node
{
int mn,upd,cnt;
}arb[4*nmax];
vector<int> a[nmax],viz[nmax];
vector<int> r,c;
int v[10],L[15],C[15];
int st,dr,n,h,w,lf,cf,i,j,nr;
void update(int nod,int l,int r,int st,int dr,int value)
{
if(st<=l&&r<=dr)
{
arb[nod].upd+=value;
return;
}
int m=(l+r)/2;
if(arb[nod].upd)
{
update(2*nod,l,m,l,m,arb[nod].upd);
update(2*nod+1,m+1,r,m+1,r,arb[nod].upd);
arb[nod].upd=0;
}
if(st<=m) update(2*nod,l,m,st,dr,value);
if(m<dr) update(2*nod+1,m+1,r,st,dr,value);
arb[nod].mn=min(arb[2*nod].mn+arb[2*nod].upd,arb[2*nod+1].mn+arb[2*nod+1].upd);
arb[nod].cnt=0;
if(arb[nod].mn==arb[2*nod].mn+arb[2*nod].upd)
arb[nod].cnt+=arb[2*nod].cnt;
if(arb[nod].mn==arb[2*nod+1].mn+arb[2*nod+1].upd)
arb[nod].cnt+=arb[2*nod+1].cnt;
}
void build(int nod,int l,int r)
{
if(l==r)
{
arb[nod].cnt=1;
return;
}
int m=(l+r)/2;
build(2*nod,l,m);
build(2*nod+1,m+1,r);
arb[nod].cnt=arb[2*nod].cnt+arb[2*nod+1].cnt;
}
void upd(int l,int c,int cat)
{
st=a[l][c];dr=min(a[l-1][c],a[l][c-1])-1;//facem update pt colt
if(st<=dr)
update(1,1,n,st,dr,cat);
//facem update pt celule din afara
for(int idx=0;idx<4;idx++)
{
lf=l+d1[idx];cf=c+d2[idx];
v[idx]=a[lf][cf];
}
sort(v,v+4);
st=v[1];dr=a[l][c]-1;
if(st<=dr)
update(1,1,n,st,dr,cat);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
r=R;c=C;
for(i=0;i<=H+1;i++)
for(j=1;j<=W+3;j++)
a[i].push_back(n+1),viz[i].push_back(0);
for(i=0;i<r.size();i++)
{
r[i]++;c[i]++;
a[r[i]][c[i]]=i+1;
}
h=H,w=W;
n=h*w;
build(1,1,n);
for(i=0;i<=h+1;i++)
a[i][0]=a[i][w+1]=n+1;
for(i=0;i<=w+1;i++)
a[0][i]=a[h+1][i]=n+1;
for(i=1;i<=h;i++)
for(j=1;j<=w;j++)
{
upd(i,j,1);
}
}
void rupe_tot(int ll,int cc)
{
if(!viz[ll][cc])
{
viz[ll][cc]=1;
++nr;
L[nr]=ll;C[nr]=cc;
}
for(int idx=0;idx<4;idx++)
{
lf=ll+d1[idx];cf=cc+d2[idx];
if((!viz[lf][cf])&&lf>=1&&cf>=1&&lf<=h&&cf<=w)
{
viz[lf][cf]=1;
++nr;
L[nr]=lf;C[nr]=cf;
}
}
}
int swap_seats(int aa, int b) {
nr=0;
rupe_tot(r[aa],c[aa]);
rupe_tot(r[b],c[b]);
for(int i=1;i<=nr;i++)
upd(L[i],C[i],-1);
swap(a[r[aa]][c[aa]],a[r[b]][c[b]]);
swap(r[aa],r[b]);swap(c[aa],c[b]);
for(int i=1;i<=nr;i++)
upd(L[i],C[i],1),viz[L[i]][C[i]]=0;
if(arb[1].mn+arb[1].upd==1) return arb[1].cnt;
return 0;
}
