#include "seats.h"
#include <bits/stdc++.h>
#define MAXN 1000005
#define INF (1 << 30)
#define VARS int mid = (l + r) / 2, lchild = (2 * node) + 1, rchild = (2 * node) + 2
using namespace std;
struct Node
{
int minim, freq;
Node operator + ( const Node& _x ) const
{
Node aux;
if ( minim < _x.minim )
aux.minim = minim, aux.freq = freq;
else if ( minim > _x.minim )
aux.minim = _x.minim, aux.freq = _x.freq;
else
aux.minim = minim, aux.freq = freq + _x.freq;
return aux;
}
void out ()
{
cout << minim << " " << freq << "\n";
}
};
int N, H, W;
vector <int> R, C, A;
vector <vector <int>> seats;
Node ST[4 * MAXN], DEFAULT;
int lazy[4 * MAXN];
void propagate ( int node, int l, int r )
{
ST[node].minim += lazy[node];
if ( l != r )
{
VARS;
lazy[lchild] += lazy[node];
lazy[rchild] += lazy[node];
}
lazy[node] = 0;
}
void build ( int node = 0, int l = 0, int r = N - 1 )
{
if ( l == r )
{
ST[node].minim = 0;
ST[node].freq = 1;
return;
}
VARS;
build ( lchild, l, mid );
build ( rchild, mid + 1, r );
ST[node] = ST[lchild] + ST[rchild];
}
void upd ( int L, int R, int x, int node = 0, int l = 0, int r = N - 1 )
{
propagate ( node, l, r );
if ( r < L or R < l )
return;
if ( L <= l && r <= R )
{
lazy[node] = x;
propagate ( node, l, r );
return;
}
VARS;
upd ( L, R, x, lchild, l, mid );
upd ( L, R, x, rchild, mid + 1, r );
ST[node] = ST[lchild] + ST[rchild];
}
Node qry ( int L, int R, int node = 0, int l = 0, int r = N - 1 )
{
propagate ( node, l, r );
if ( r < L or R < l )
return DEFAULT;
if ( L <= l && r <= R )
return ST[node];
VARS;
return qry ( L, R, lchild, l, mid ) + qry ( L, R, rchild, mid + 1, r );
}
void give_initial_chart ( int _h, int _w, vector <int> _r, vector <int> _c )
{
DEFAULT.minim = INF;
DEFAULT.freq = 0;
H = _h;
W = _w;
N = H * W;
swap ( R, _r );
swap ( C, _c );
seats.resize ( H + 5 );
for ( int i = 0; i < H + 5; i++ )
seats[i].resize ( W + 5 );
for ( int i = 0; i <= W + 1; i++ )
seats[0][i] = N, seats[H + 1][i] = N;
for ( int i = 0; i <= H + 1; i++ )
seats[i][0] = N, seats[i][W + 1] = N;
for ( int i = 0; i < N; i++ )
seats[R[i] + 1][C[i] + 1] = i;
build ( );
for ( int i = 0; i <= H; i++ )
{
for ( int j = 0; j <= W; j++ )
{
A.clear();
A.push_back ( seats[i][j] );
A.push_back ( seats[i][j + 1] );
A.push_back ( seats[i + 1][j] );
A.push_back ( seats[i + 1][j + 1] );
sort ( A.begin(), A.end() );
upd ( A[0], A[1] - 1, 1 );
upd ( A[2], A[3] - 1, 1 );
}
}
}
int swap_seats ( int a, int b )
{
for ( int i = R[a]; i <= R[a] + 1; i++ )
{
for ( int j = C[a]; j <= C[a] + 1; j++ )
{
A.clear();
A.push_back ( seats[i][j] );
A.push_back ( seats[i][j + 1] );
A.push_back ( seats[i + 1][j] );
A.push_back ( seats[i + 1][j + 1] );
sort ( A.begin(), A.end() );
upd ( A[0], A[1] - 1, -1 );
upd ( A[2], A[3] - 1, -1 );
}
}
for ( int i = R[b]; i <= R[b] + 1; i++ )
{
for ( int j = C[b]; j <= C[b] + 1; j++ )
{
A.clear();
A.push_back ( seats[i][j] );
A.push_back ( seats[i][j + 1] );
A.push_back ( seats[i + 1][j] );
A.push_back ( seats[i + 1][j + 1] );
sort ( A.begin(), A.end() );
upd ( A[0], A[1] - 1, -1 );
upd ( A[2], A[3] - 1, -1 );
}
}
swap ( seats[R[a] + 1][C[a] + 1], seats[R[b] + 1][C[b] + 1] );
swap ( R[a], R[b] );
swap ( C[a], C[b] );
for ( int i = R[a]; i <= R[a] + 1; i++ )
{
for ( int j = C[a]; j <= C[a] + 1; j++ )
{
A.clear();
A.push_back ( seats[i][j] );
A.push_back ( seats[i][j + 1] );
A.push_back ( seats[i + 1][j] );
A.push_back ( seats[i + 1][j + 1] );
sort ( A.begin(), A.end() );
upd ( A[0], A[1] - 1, 1 );
upd ( A[2], A[3] - 1, 1 );
}
}
for ( int i = R[b]; i <= R[b] + 1; i++ )
{
for ( int j = C[b]; j <= C[b] + 1; j++ )
{
A.clear();
A.push_back ( seats[i][j] );
A.push_back ( seats[i][j + 1] );
A.push_back ( seats[i + 1][j] );
A.push_back ( seats[i + 1][j + 1] );
sort ( A.begin(), A.end() );
upd ( A[0], A[1] - 1, 1 );
upd ( A[2], A[3] - 1, 1 );
}
}
propagate ( 0, 0, N - 1 );
if ( ST[0].minim == 4 )
return ST[0].freq;
return 0;
}
