#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>
#include "seats.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=1;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define fornb(i,n) for(int i=n-1;i>0;i--)
#define maxl 10000000000
#define con continue;
typedef long long lol;
using namespace std;
typedef vector<int> veci;
typedef pair<lol,lol> point;
lol sum=0;
vector<int> r,c;
vector<veci> all;
veci minr,minc;
int h,w;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
r = R;
c = C;
h=H;
w=W;
all.resize(H);
fori(i,H){
all[i].resize(W);
}
fori(i,h*w){
all[r[i]][c[i]]=i;
}
minr.resize(H);
fori(i,H){
int mini=h*w;
fori(j,w){
mini=min(mini,all[i][j]);
}
minr[i]=mini;
}
minc.resize(w);
fori(j,w){
int mini=h*w;
fori(i,H){
mini=min(mini,all[i][j]);
}
minc[j]=mini;
}
}
int calculate(){
int sum=1;
int R=r[0];
int C=c[0];
int rows=1,cols=1;
veci rr;
int minn=h*w;
fori(i,R){
minn=min(minn,minr[i]);
rr.push_back(minn);
}
minn=h*w;
forib(i,h){
if(i==R){
break;
}
minn=min(minn,minr[i]);
rr.push_back(minn);
}
veci cc;
minn=h*w;
fori(i,C){
minn=min(minn,minc[i]);
cc.push_back(minn);
}
minn=h*w;
forib(i,w){
if(i==C){
break;
}
minn=min(minn,minc[i]);
cc.push_back(minn);
}
sort(rr.begin(),rr.end());
sort(cc.begin(),cc.end());
int i=0,j=0;
while(i<h-1 && j<w-1){
if(rows*cols<=rr[i] && rows*cols<=cc[j]){
sum++;
}
if(rr[i]<cc[j]){
rows++;
i++;
}else{
cols++;
j++;
}
}
while(i<h-1){
if(rows*cols<=rr[i]){
sum++;
}
rows++;
i++;
}
while(j<w-1){
if(rows*cols<=cc[j]){
sum++;
}
cols++;
j++;
}
return sum;
}
int swap_seats(int a, int b) {
swap(c[a],c[b]);
swap(r[a],r[b]);
swap(all[r[a]][c[a]],all[r[b]][c[b]]);
int i=r[a];
int mini=h*w;
fori(j,w){
mini=min(mini,all[i][j]);
}
minr[i]=mini;
i=r[b];
mini=h*w;
fori(j,w){
mini=min(mini,all[i][j]);
}
minr[i]=mini;
int j=c[a];
mini=h*w;
fori(i,h){
mini=min(mini,all[i][j]);
}
minc[j]=mini;
j=c[b];
mini=h*w;
fori(i,h){
mini=min(mini,all[i][j]);
}
minc[j]=mini;
return calculate();
}
