#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
const int nmax=1e6+42;
int n,m;
pair<int,int> where[nmax];
vector< vector<int> > inp;
int cnt[nmax][5];
int ask(int x,int y)
{
if(0>x||x>=n||0>y||y>=m)return 1e9;
return inp[x][y];
}
void eval(int x,int y)
{
if(0>x||x>=n||0>y||y>=m)return;
int cur[5]={0,0,0,0,0};
int help;
help=1+(ask(x-1,y-1)<inp[x][y])+(ask(x-1,y)<inp[x][y])+(ask(x,y-1)<inp[x][y]);
cur[help]++;
help=1+(ask(x-1,y)<inp[x][y])+(ask(x-1,y+1)<inp[x][y])+(ask(x,y+1)<inp[x][y]);
cur[help]++;
help=1+(ask(x,y-1)<inp[x][y])+(ask(x+1,y-1)<inp[x][y])+(ask(x+1,y)<inp[x][y]);
cur[help]++;
help=1+(ask(x,y+1)<inp[x][y])+(ask(x+1,y+1)<inp[x][y])+(ask(x+1,y)<inp[x][y]);
cur[help]++;
for(int i=0;i<5;i++)
cnt[inp[x][y]][i]=0;
for(int i=1;i<5;i++)
{
cnt[inp[x][y]][i]+=cur[i];
cnt[inp[x][y]][i-1]-=cur[i];
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
n=H;
m=W;
for(int t=0;t<n*m;t++)
{
int i=R[t];
int j=C[t];
while(inp.size()<=i)inp.push_back({});
while(inp[i].size()<=j)inp[i].push_back(j);
where[t]={i,j};
inp[i][j]=t;
}
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
eval(i,j);
}
int swap_seats(int a, int b)
{
swap(inp[where[a].first][where[a].second],inp[where[b].first][where[b].second]);
swap(where[a],where[b]);
for(int x=-1;x<=1;x++)
for(int y=-1;y<=1;y++)
{
eval(where[a].first+x,where[a].second+y);
eval(where[b].first+x,where[b].second+y);
}
int pref[5]={0,0,0,0,0};
int outp=0;
for(int i=0;i<n*m;i++)
{
for(int j=0;j<5;j++)
pref[j]+=cnt[i][j];
if(pref[1]==4&&pref[3]==0)outp++;
//cout<<"i: "<<i<<" pref: ";for(int j=0;j<5;j++)cout<<pref[j]<<" ";cout<<endl;
}
return outp;
}
/*
int main() {
int H = read_int();
int W = read_int();
int Q = read_int();
std::vector<int> R(H * W), C(H * W);
for (int i = 0; i < H * W; ++i) {
R[i] = read_int();
C[i] = read_int();
}
std::vector<int> A(Q), B(Q);
for (int j = 0; j < Q; ++j) {
A[j] = read_int();
B[j] = read_int();
}
give_initial_chart(H, W, R, C);
for (int j = 0; j < Q; ++j) {
int answer = swap_seats(A[j], B[j]);
printf("%d\n", answer);
}
return 0;
}
*/
