#include "seats.h"
#include <bits/stdc++.h>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;
struct Extremums {
int xMin, xMax, yMin, yMax;
int aire(){
return (yMax - yMin + 1) * (xMax - xMin + 1);
}
void debug(){
;//cout << xMin << " " << xMax << " " << yMin << " " << yMax << endl;
}
};
struct Point {
int x, y;
};
int nLigs, nCols, nVals;
const int MAX_VALS = (1 << 20);
const int N = MAX_VALS;
Extremums vals[2 * MAX_VALS];
bool estOk[MAX_VALS];
Point points[MAX_VALS];
int sum = 0;
void combine(int noeud){
vals[noeud].xMin = min(vals[noeud * 2].xMin, vals[noeud * 2 + 1].xMin);
vals[noeud].xMax = max(vals[noeud * 2].xMax, vals[noeud * 2 + 1].xMax);
vals[noeud].yMin = min(vals[noeud * 2].yMin, vals[noeud * 2 + 1].yMin);
vals[noeud].yMax = max(vals[noeud * 2].yMax, vals[noeud * 2 + 1].yMax);
/*
if (noeud == 524288){
cout << "wsh wsh\n";
vals[noeud * 2].debug();
vals[noeud * 2 + 1].debug();
cout << "----\n";
}*/
}
Extremums combiner(Extremums a, Extremums b){
return {min(a.xMin, b.xMin), max(a.xMax, b.xMax), min(a.yMin, b.yMin), max(a.yMax, b.yMax)};
}
void update(int noeud){
noeud /= 2;
for (; noeud > 0; noeud /= 2)
combine(noeud);
}
Extremums get(int gauche, int droite){
//cout << "get " << gauche << " " << droite << endl;
if (droite < gauche) return {N, -1, N, -1};
if (gauche%2 == 1) return combiner(vals[gauche], get(gauche + 1, droite));
if (droite%2 == 0) return combiner(vals[droite], get(gauche, droite - 1));
return get(gauche/2, droite/2);
}
void construire(int iVal){
vals[N + iVal] = {points[iVal].x, points[iVal].x, points[iVal].y, points[iVal].y};
update(N + iVal);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
for (int noeud = 0; noeud < 2 * N; ++noeud)
vals[noeud] = {N, -1, N, -1};
nLigs = H;
nCols = W;
nVals = nLigs * nCols;
for (int iVal = 0; iVal < nVals; ++iVal)
points[iVal] = {R[iVal], C[iVal]};
for (int iVal = 0; iVal < nVals; ++iVal)
construire(iVal);
}
int getOpt(){
sum = 0;
int pointeur = 0;
//cout << "REQ\n";
int noeud = 524288;
vals[noeud].debug();
while (pointeur < nVals){
Extremums nxt;
while ((nxt = get(N, N + pointeur)).aire() != pointeur + 1){
//cout << "boucle " << pointeur << " " << nxt.aire() << endl;
//cout << nxt.xMin << " " << nxt.xMax << " " << nxt.yMin << " " << nxt.yMax << endl << endl;
pointeur = nxt.aire() - 1;
}
sum++;
//cout << "jsp " << pointeur << endl;
//Extremums a = nxt;
//cout << a.xMin << " " << a.xMax << " " << a.yMin << " " << a.yMax << " " << a.aire() << endl;
pointeur++;
}
return sum;
}
int swap_seats(int a, int b) {
swap(points[a], points[b]);
vals[N + a] = {points[a].x, points[a].x, points[a].y, points[a].y};
vals[N + b] = {points[b].x, points[b].x, points[b].y, points[b].y};
update(N + a);
update(N + b);
if (true)
return getOpt();
for (int iVal = min(a, b); iVal <= max(a, b); ++iVal)
construire(iVal);
return sum;
}
