// moreflags=grader.cpp
// 8
// ...
#include "seats.h"
#include<vector>
#include<algorithm>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
struct MyData{
static int constexpr blockSize=
#if LOCAL
100
#else
1000
#endif
;
struct Pos{int row, col;};
struct Rectangle{Pos minimum, maximum;
Rectangle& operator+=(Rectangle other){
minimum.row=std::min(minimum.row, other.minimum.row);
minimum.col=std::min(minimum.col, other.minimum.col);
maximum.row=std::max(maximum.row, other.maximum.row);
maximum.col=std::max(maximum.col, other.maximum.col);
return *this;
}
Rectangle operator+(Rectangle other) const{return other+=*this;}
int area() const{
assert(maximum.row>minimum.row);
assert(maximum.col>minimum.col);
return (maximum.row-minimum.row)*(maximum.col-minimum.col);
}
bool contains(Rectangle other) const{return area()==(*this+other).area();}
static Rectangle from(Pos it){return Rectangle{it, {it.row+1, it.col+1}};}
};
struct Cover{Rectangle bound; int missing;
int count() const{
assert(missing<=bound.area());
return bound.area()-missing;
};
Cover operator+(Cover other) const{
auto const resultBound=bound+other.bound;
auto const resultMissing=resultBound.area()-count()-other.count();
assert(resultMissing>=0);
return {resultBound, resultMissing};
}
};
struct Block{
std::vector<Cover> cover;
std::array<Pos, blockSize> items;
int number;
void build(){ // recompute necessary information after items changes
assert(number<=blockSize);
assert(number!=0);
cover.clear();
cover.push_back({Rectangle::from(items[0]), 0});
for(int index=1; index<number; ++index){
auto& [prevBound, prevMissing]=cover.back();
auto const next=Rectangle::from(items[index])+prevBound;
auto const diff=next.area()-prevBound.area();
assert(diff>=0);
if(diff==0){
assert(prevMissing>0);
--prevMissing;
}else{
cover.push_back({next, prevMissing+diff-1});
}
}
}
void setWithoutBuild(int index, Pos pos){
assert(index<number);
items[index]=pos;
}
std::pair<int, Cover> get(Cover const previous)const{
int result=0;
int lastContain=-1;
for(int step=1<<(31^__builtin_clz((int)cover.size())); step; step>>=1)
if(lastContain+step<(int)cover.size() and
previous.bound.contains(cover[lastContain+step].bound))
lastContain+=step;
// now lastContain=last inside previous
if(lastContain>=0 and (previous+cover[lastContain]).missing==0)
++result;
for(int pos=0; pos<lastContain; ++pos)
assert((previous+cover[pos]).missing!=0);
int pos=lastContain+1;
while(pos<(int)cover.size()){ // this outer loop will only run for O(1) iterations
if(cover[pos].bound.contains(previous.bound)){
while(pos<(int)cover.size()){
assert(
((previous+cover[pos]).missing==0) ==
(cover[pos].missing==previous.count())
);
if(cover[pos].missing==previous.count()) ++result;
++pos;
}
break;
}
assert(not previous.bound.contains(cover[pos].bound));
auto const target=cover[pos].bound+previous.bound;
auto const oldPos=pos;
--pos;
for(int step=1<<(31^__builtin_clz((int)cover.size())); step; step>>=1)
if(pos+step<(int)cover.size() and
not (cover[pos+step].bound+previous.bound).contains(target))
pos+=step;
assert(pos<oldPos or not (cover[pos].bound+previous.bound).contains(target));
++pos; // now pos=first contains target after joined with previous
for(int pos1=oldPos; pos1<pos; ++pos1)
assert((previous+cover[pos1]).missing!=0);
if(pos==(int)cover.size()) break;
assert((cover[pos].bound+previous.bound).contains(target));
if((previous+cover[pos]).missing==0) ++result;
++pos;
}
return {result, previous+cover.back()};
}
};
int number;
std::vector<Block> data;
MyData(){}
MyData(int const number, std::vector<int> const& R, std::vector<int> const& C):
number(number), data((number-1)/blockSize+1)
{
assert(number!=0);
for(auto& it: data) it.number=blockSize;
data.back().number-=(int)data.size()*blockSize-number;
assert((int)R.size()==number); assert((int)C.size()==number);
for(int block=0; block<(int)data.size(); ++block)
for(int index=0; index<data[block].number; ++index)
data[block].items[index]={R[block*blockSize+index], C[block*blockSize+index]};
for(auto& it: data) it.build();
}
int getResult(){
Cover current{Rectangle::from(data[0].items[0]), 1};
int result{};
for(auto const& it: data){
auto [count, next]=it.get(current);
result+=count; current=next;
}
assert(current.missing==0); assert(result>0);
return result;
}
Pos get(int index) const{
assert(0<=index); assert(index<number);
return data[index/blockSize].items[index%blockSize];
}
int swap(int first, int sec){
auto const x=get(first), y=get(sec);
data[first/blockSize].setWithoutBuild(first%blockSize, y);
data[sec/blockSize].setWithoutBuild(sec%blockSize, x);
data[first/blockSize].build();
if(first/blockSize!=sec/blockSize)
data[sec/blockSize].build();
return getResult();
}
} myData;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
myData=MyData{H*W, R, C};
}
int swap_seats(int a, int b) {
return myData.swap(a, b);
}
