#include "seats.h"
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
const int NB_FEUILLES = (1 << 20);
const int INFINI = NB_FEUILLES;
pair<int, int> modifs[2 * NB_FEUILLES];
int nombres[2 * NB_FEUILLES][5];
int nbLigs, nbCols;
vector<pair<int, int>> coords;
vector<vector<int>> sieges;
void update(int noeud) {
for(int i = 0;i < 5;i++) {
nombres[noeud][i] = 0;
}
if(noeud >= NB_FEUILLES) {
if(modifs[noeud].second == 0 && modifs[noeud].first <= 4) {
nombres[noeud][modifs[noeud].first]++;
}
return;
}
if(modifs[noeud].second == 0) {
for(int i = 0;i < 5;i++) {
if(i - modifs[noeud].first >= 0) {
nombres[noeud][i] += nombres[2 * noeud][i - modifs[noeud].first];
nombres[noeud][i] += nombres[2 * noeud + 1][i - modifs[noeud].first];
}
}
}
}
int nbRectangles() {
return nbLigs * nbCols + nombres[1][4] - NB_FEUILLES;
}
void ajoute(int deb, int fin, pair<int, int> modif, int n = 1, int d = 0, int f = NB_FEUILLES) {
if(deb >= f || d >= fin)
return;
if(deb <= d && f <= fin) {
modifs[n].first += modif.first;
modifs[n].second += modif.second;
update(n);
return;
}
int m = (d + f) / 2;
ajoute(deb, fin, modif, 2 * n, d, m);
ajoute(deb, fin, modif, 2 * n + 1, m, f);
update(n);
}
void update(int lig, int col, int sens) {
if(lig < 0 || col < 0 || lig > nbLigs || col > nbCols)
return;
vector<int> vals;
vals.push_back(sieges[lig][col]);
vals.push_back(sieges[lig + 1][col]);
vals.push_back(sieges[lig + 1][col + 1]);
vals.push_back(sieges[lig][col + 1]);
sort(vals.begin(), vals.end());
ajoute(vals[0], vals[1], {sens, 0});
ajoute(vals[2], vals[3], {0, sens});
}
void give_initial_chart(int _nbLigs, int _nbCols, vector<int> ligs, vector<int> cols) {
nbLigs = _nbLigs;
nbCols = _nbCols;
sieges = vector<vector<int>>(nbLigs + 2, vector<int>(nbCols + 2, INFINI));
for(int iEleve = 0;iEleve < nbLigs * nbCols;iEleve++) {
coords.push_back({ligs[iEleve] + 1, cols[iEleve] + 1});
sieges[ligs[iEleve] + 1][cols[iEleve] + 1] = iEleve;
}
for(int iSommet = 2 * NB_FEUILLES - 1;iSommet >= 1;iSommet--) {
update(iSommet);
}
for(int iLig = 0;iLig < nbLigs + 2;iLig++) {
for(int iCol = 0;iCol < nbCols + 2;iCol++) {
update(iLig, iCol, 1);
}
}
}
void ajoutePos(int lig, int col, set<pair<int, int>>& pos) {
pos.insert({lig - 1, col - 1});
pos.insert({lig - 1, col});
pos.insert({lig, col - 1});
pos.insert({lig, col});
}
int swap_seats(int a, int b) {
set<pair<int, int>> positions;
ajoutePos(coords[a].first, coords[a].second, positions);
ajoutePos(coords[b].first, coords[b].second, positions);
for(pair<int, int> pos : positions) {
update(pos.first, pos.second, -1);
}
swap(sieges[coords[a].first][coords[a].second], sieges[coords[b].first][coords[b].second]);
swap(coords[a], coords[b]);
for(pair<int, int> pos : positions) {
update(pos.first, pos.second, 1);
}
/*for(int iLig = 0;iLig < nbLigs + 2;iLig++) {
for(int iCol = 0;iCol < nbCols + 2;iCol++) {
cout << sieges[iLig][iCol] << " ";
}
cout << endl;
}*/
return nbRectangles();
}
