#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef pair<ll, int> T;
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define ins insert
#define all(x) begin(x), end(x)
const ll INF = 1e18;
T ID = mp(INF, 0);
T comb(T a, T b){
if(a.f == b.f) return mp(a.f, a.s+b.s);
return min(a, b);
}
const int SZ = 1048576;
T seg[2*SZ];
ll lazy[2*SZ];
void pull(int ind){
seg[ind] = comb(seg[2*ind], seg[2*ind+1]);
}
void push(int ind, int L, int R){
seg[ind].f+=lazy[ind];
if(L < R){
for(int i = 0; i < 2; i++){
lazy[2*ind+i]+=lazy[ind];
}
}
lazy[ind] = 0;
return;
}
void upd(int lo, int hi, ll inc, int ind = 1, int L = 0, int R = SZ-1){
push(ind, L, R);
if(L > hi || R < lo) return;
if(lo <= L && R <= hi){
lazy[ind] = inc;
push(ind, L, R);
//cout << "UPD " << ind << " " << L << " " << R << " " << seg[ind].f << " " << seg[ind].s << "\n";
return;
}
int M = (L+R)/2;
upd(lo, hi, inc, 2*ind, L, M); upd(lo, hi, inc, 2*ind+1, M+1, R);
pull(ind);
}
T query(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1){
push(ind, L, R);
if(L > hi || R < lo) return ID;
if(lo <= L && R <= hi){
//cout << ind << "\n";
return seg[ind];
}
int M = (L+R)/2;
return comb(query(lo, hi, 2*ind, L, M), query(lo, hi, 2*ind+1, M+1, R));
}
const int mx = 1000005;
int H, W;
pi pos[mx];
vector<vi> stu;
vpi rec = vpi{mp(0, 0), mp(0, 1), mp(1, 0), mp(1, 1)};
vpi rec2 = vpi{mp(-1, -1), mp(-1, 0), mp(0, -1), mp(0, 0)};
vector<pair<pi, bool>> fig[8];
ll val[8];
vector<pair<pi, int>> rot;
bool works(int r, int c, pi dif){
r = r+dif.f;
c = c+dif.s;
if(r < 0 || H-1 < r) return 0;
if(c < 0 || W-1 < c) return 0;
return 1;
}
bool mode = 0;
ll csum[mx];
void updSeat(int r, int c, int con, int typ){
bool good = 1;
int lo = 0;
int hi = H*W-1;
for(auto u: fig[con]){
if(!works(r, c, u.f)){
good = 0;
//cout << "NO WORK " << r << " " << c << " " << con << "\n";
break;
}
if(u.s == 1){
lo = max(lo, stu[r+u.f.f][c+u.f.s]);
}
else{
hi = min(hi, stu[r+u.f.f][c+u.f.s]-1);
}
}
if(lo > hi) good = 0;
if(!good) return;
// cout << "updSeat: " << r << " " << c << " " << con << " " << typ << "\n";
// cout << "seg update " << lo << " " << hi << " " << val[con]*typ << "\n";
if(mode == 0){
csum[lo]+=val[con]*typ;
csum[hi+1]-=val[con]*typ;
}
else upd(lo, hi, val[con]*typ);
}
void give_initial_chart(int _H, int _W, vi R, vi C) {
for(int i = 0; i < 5; i++){
for(int k = 0; k < 4; k++){
bool x = 1;
if(i == k) x = 0;
fig[i].pb(mp(rec[k], x));
}
}
for(int i = 5; i < 8; i++){
fig[i].pb(mp(mp(0, 0), 1));
}
fig[6].pb(mp(mp(0, 1), 1));
fig[7].pb(mp(mp(1, 0), 1));
val[0] = val[1] = val[2] = val[3] = 1000000000LL;
val[4] = 1;
val[5] = 1;
val[6] = -1;
val[7] = -1;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 5; j++){
rot.pb(mp(rec2[i], j));
}
}
for(int i = 5; i < 8; i++){
rot.pb(mp(mp(0, 0), i));
}
rot.pb(mp(rec2[2], 6));
rot.pb(mp(rec2[1], 7));
// cout << "rot:\n";
// for(auto u: rot){
// cout << u.f.f << " " << u.f.s << " " << u.s << "\n";
// }
// cout << "\n";
// for(int i = 0; i < 4; i++){
// int r = rec1[i].f;
// int c = rec1[i].s;
// for(int j = 0; j < 4; j++){
// for(int k = 0; k < 4; k++){
// bool x = 1;
// if(j == k) x = 0;
// fig[4*i+j].pb(mp(mp(r+rec2[k].f, c+rec2[k].s), x));
// }
// val[4*i+j] = 1000000000LL;
// }
// }
// for(int i = 0; i < 4; i++){
// int r = rec1[i].f;
// int c = rec1[i].s;
// for(int k = 0; k < 4; k++){
// fig[16+i].pb(mp(mp(r+rec2[k].f, c+rec2[k].s), 1));
// }
// val[16+i] = 1;
// }
// for(int i = 0; i <= 4; i++){
// fig[20+i].pb(mp(mp(0, 0), 1));
// }
// fig[21].pb(mp(mp(0, -1), 1));
// fig[22].pb(mp(mp(0, 1), 1));
// fig[23].pb(mp(mp(-1, 0), 1));
// fig[24].pb(mp(mp(1, 0), 1));
// val[20] = 1;
// val[21] = val[22] = val[23] = val[24] = -1;
for(int i = SZ; i < 2*SZ; i++){
seg[i] = mp(0, 1);
}
// cout << seg[1+SZ].f << " " << seg[1+SZ].s << "\n";
// T q1 = query(1, 1);
// cout << q1.f << " " << q1.s << "\n";
// upd(1, 1, 5);
// q1 = query(1, 1);
// cout << q1.f << " " << q1.s << "\n";
// cout << "////////////////\n";
H = _H;
W = _W;
stu = vector<vi>(H, vi(W, 0));
for(int i = 0; i < H*W; i++){
pos[i] = mp(R[i], C[i]);
stu[R[i]][C[i]] = i;
}
for(int i = 0; i < H; i++){
for(int j = 0; j < W; j++){
for(int k = 0; k < 8; k++){
updSeat(i, j, k, 1);
}
}
}
for(int i = 1; i < H*W; i++){
csum[i]+=csum[i-1];
}
for(int i = 0; i < H*W; i++){
seg[i+SZ] = mp(csum[i], 1);
}
for(int i = SZ-1; i >= 1; i--){
pull(i);
}
mode = 1;
// for(int i = 0; i < H*W; i++){
// T q1 = query(i, i);
// cout << "query " << i << " " << q1.f << " " << q1.s << "\n";;
// }
// T q1 = query(0, H*W-1);
// cout << "query " << " " << q1.f << " " << q1.s << "\n";
}
int swap_seats(int a, int b) {
//cout << "swap_seats " << a << " " << b << "\n";
pi pos1 = pos[a];
pi pos2 = pos[b];
vector<pair<pi, int>> upds;
for(auto u: rot){
upds.pb(mp(mp(pos1.f+u.f.f, pos1.s+u.f.s), u.s));
}
for(auto u: rot){
upds.pb(mp(mp(pos2.f+u.f.f, pos2.s+u.f.s), u.s));
}
// for(auto u: upds){
// cout << "upds " << u.f.f << " " << u.f.s << " " << u.s << " " << "\n";
// }
sort(all(upds));
upds.erase(unique(all(upds)), end(upds));
for(auto u: upds){
updSeat(u.f.f, u.f.s, u.s, -1);
}
swap(pos[a], pos[b]);
swap(stu[pos1.f][pos1.s], stu[pos2.f][pos2.s]);
for(auto u: upds){
updSeat(u.f.f, u.f.s, u.s, 1);
}
// for(int i = 0; i < H*W; i++){
// T q1 = query(i, i);
// cout << "query " << i << " " << q1.f << " " << q1.s << "\n";;
// }
T q = query(0, H*W-1);
assert(q.f == 1);
return q.s;
}
