#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int n, h, w;
vector<int> r, c;
int MxC[4*maxn], MxR[4*maxn], MnC[4*maxn], MnR[4*maxn];
void change(int id, int L, int R, int idx){
if (L+1 == R){
MxR[id] = MnR[id] = r[L];
MxC[id] = MnC[id] = c[L];
return;
}
int mid = (L + R) >> 1;
int lc = 2*id+0, rc = 2*id+1;
if (idx < mid)
change(lc, L, mid, idx);
else
change(rc, mid, R, idx);
MxC[id] = max(MxC[lc], MxC[rc]);
MxR[id] = max(MxR[lc], MxR[rc]);
MnC[id] = max(MnC[lc], MnC[rc]);
MnR[id] = max(MnR[lc], MnR[rc]);
}
pair<int,int> merge(pair<int,int> fi, pair<int,int> se){
return {min(fi.first,se.first), min(fi.second,se.second)};
}
pair<int,int> getR(int id, int L, int R, int idx){
if (L+1 == R)
return {MnR[id],MxR[id]};
int mid = (L + R) >> 1;
auto it = getR(2*id+0, L, mid, idx);
if (mid < idx)
it = merge(it,getR(2*id+1,mid,R,idx));
return it;
}
pair<int,int> getC(int id, int L, int R, int idx){
if (L+1 == R)
return {MnC[id],MxC[id]};
int mid = (L + R) >> 1;
auto it = getC(2*id+0, L, mid, idx);
if (mid < idx)
it = merge(it,getC(2*id+1,mid,R,idx));
return it;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h = H, w = W, r = R, c = C;
n = h*w;
for (int i = 0; i < n; i++)
change(1, 0, n, i);
}
bool isGood(int &r1, int &r2, int &c1, int &c2){
int Size = (r2-r1+1) * (c2-c1+1);
auto it = getR(1, 0, n, Size);
if (it.second > r2){
r2 ++;
return false;
}
if (it.first < r1){
r1 --;
return false;
}
it = getC(1, 0, n, Size);
if (it.second > c2){
c2 ++;
return false;
}
if (it.first < c1){
c1 --;
return false;
}
if (r[Size] < r1)
r1 --;
else if (r[Size] > r2)
r2 ++;
else if (c[Size] < c1)
c1 --;
else
c2 ++;
return true;
}
int swap_seats(int a, int b){
swap(r[a],r[b]);
swap(c[a],c[b]);
change(1, 0, n, a);
change(1, 0, n, b);
int r1 = r[0], r2 = r[0], c1 = c[0], c2 = c[0], ret = 0;
int Size = 1;
while (Size < n){
int tmp = isGood(r1, r2, c1, c2);
cout << tmp << endl;
ret += tmp;
Size = (r2-r1+1) * (c2-c1+1);
}
ret ++; // h*w
return ret;
}
