#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define debug(a) cout << #a << " = " << a << endl
struct x{
int MAXf;
int MINf;
int MAXc;
int MINc;
int hizq;
int hder;
};
struct y{
int fil;
int col;
};
int cont,n,p,res;
x uso,maximos;
x ST[2100000];
y id[1000002];
void d(int p){
x nodo;
debug(p);
nodo = ST[p];
debug(nodo.MAXf);
debug(nodo.MINf);
debug(nodo.MAXc);
debug(nodo.MINc);
debug(nodo.hizq);
debug(nodo.hder);
debug(" ");
}
void h(int pos){
ST[pos].hizq = cont++;
ST[pos].hder = cont++;
}
x crea(int ini, int fin, int num, x des, int pos) {
x a,b;
int mitad;
if (ini == fin && ini == num) {
ST[pos].MAXf = des.MAXf;
ST[pos].MAXc = des.MAXc;
ST[pos].MINf = des.MINf;
ST[pos].MINc = des.MINc;
return ST[pos];
}
else if (ini <= num && fin >= num) {
mitad = (ini+fin) / 2;
if (ST[pos].hizq == 0) h(pos);
a = crea(ini, mitad, num, des, ST[pos].hizq);
b = crea(mitad + 1, fin, num, des, ST[pos].hder);
ST[pos].MAXf = max(ST[ST[pos].hizq].MAXf, ST[ST[pos].hder].MAXf);
ST[pos].MINf = min(ST[ST[pos].hizq].MINf, ST[ST[pos].hder].MINf);
ST[pos].MAXc = max(ST[ST[pos].hizq].MAXc, ST[ST[pos].hder].MAXc);
ST[pos].MINc = min(ST[ST[pos].hizq].MINc, ST[ST[pos].hder].MINc);
return ST[pos];
}
return {0, 1000002, 0, 1000002, 0, 0};
}
x query(int nodo, int ini, int fin, int r) {
int mitad;
x a,b;
if (fin <= r) {
return ST[nodo];
}
else if (ini <= r) {
mitad = (ini+fin) / 2;
a = query(ST[nodo].hizq,ini,mitad, r);
b = query(ST[nodo].hder,mitad+1,fin, r);
a.MAXf = max(a.MAXf, b.MAXf);
a.MINf = min(a.MINf, b.MINf);
a.MAXc = max(a.MAXc, b.MAXc);
a.MINc = min(a.MINc, b.MINc);
return a;
}
return {0, 1000002,0, 1000002,0,0};
}
bool checa(x act, int val) {
int l1,l2;
l1 = act.MAXf - act.MINf + 1;
l2 = act.MAXc - act.MINc + 1;
l1 *= l2;
return (l1 == (val+1));
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H*W;
cont = 2;
rep(i, 0, n-1) {
id[i] = {R[i], C[i]};
uso = {R[i], R[i], C[i], C[i], 0, 0};
uso = crea(0, n-1, i, uso, 1);
}
}
int swap_seats(int a, int b) {
uso = {id[a].fil, id[a].fil, id[a].col, id[a].col,0,0};
crea(0, n-1, b, uso, 1);
uso = {id[b].fil, id[b].fil, id[b].col, id[b].col,0,0};
crea(0, n-1, a, uso, 1);
swap(id[a], id[b]);
p = 0;
maximos = {id[p].fil, id[p].fil, id[p].col, id[p].col, 0 ,0};
res = 0;
while (p < n) {
maximos = query(1, 0, n-1, p);
if (checa(maximos, p)) {
res++;
p++;
}
else {
p = (maximos.MAXf - maximos.MINf + 1) * (maximos.MAXc - maximos.MINc + 1) - 1;
}
}
return res;
}
