// moreflags=grader.cpp
// 6
// late
// One of my worst performances so far.
// At least I decided to switch to problem 3 and got 49 points there.
// Almost everyone got 37 points for this problem...
// Figuring out the optimal solution during the contest time is good,
// but not if the optimal solution has some logical error (even if they're patchable)
// or it's too complex to implement...
//
#include "seats.h"
#include<vector>
#include<climits>
#include<algorithm>
#if LOCAL
#include<iostream>
#else
#define NDEBUG
#endif
#include<cassert>
struct MyData{
static int constexpr blockSize=
#if LOCAL
3
#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;}
Rectangle intersectUnchecked(Rectangle other) const{
Rectangle const result={
{
std::max(minimum.row, other.minimum.row),
std::max(minimum.col, other.minimum.col)
},
{
std::min(maximum.row, other.maximum.row),
std::min(maximum.col, other.maximum.col)
}
};
return result;
}
bool valid() const{
return maximum.row>=minimum.row and maximum.col>=minimum.col;
}
int area() const{
assert(valid());
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 Max2D{
std::vector<std::vector<int>> data;
Max2D(int numRow=0, int numCol=0): data(numRow*2, std::vector<int>(numCol*2)){}
int get(int first, int sec, int third, int forth)const{
first+=int(data.size()/2); sec+=int(data.size()/2);
third+=int(data[0].size()/2); forth+=int(data[0].size()/2);
assert(first<sec); assert(third<forth);
int result=INT_MIN;
auto const process=[&](int nodeIndex){
auto const& node=data[nodeIndex];
for(int first=third, sec=forth; first<sec; first>>=1, sec>>=1){
if(first&1) result=std::max(result, node[first++]);
if(sec&1) result=std::max(result, node[--sec]);
}
};
for(;first<sec; first>>=1, sec>>=1){
if(first&1) process(first++);
if(sec&1) process(--sec);
}
return result;
}
int get(int first, int sec)const{
first+=int(data.size()/2);
sec+=int(data[0].size()/2);
return data[first][sec];
}
void set(int first, int sec, int value){
first+=int(data.size()/2);
sec+=int(data[0].size()/2);
data[first][sec]=value;
for(int third=first; third>>=1;)
data[third][sec]=std::max(data[third*2][sec], data[third*2+1][sec]);
for(int third=first; third; third>>=1)
for(int forth=sec; forth>>=1;)
data[third][forth]=std::max(data[third][forth*2], data[third][forth*2+1]);
}
};
struct Block{
struct T{Cover cover; int index;};
std::vector<T> cover;
struct MinInfo{
int count, value;
MinInfo operator+(int other)const{
if(value<other) return *this;
if(value>other) return {1, other};
return {count+1, value};
}
MinInfo operator+(MinInfo other)const{ // commutative
if(value<other.value) return *this;
if(value>other.value) return other;
return {count+other.count, value};
}
};
//std::vector<MinInfo> suffix;
std::array<Pos, blockSize> items;
std::vector<MinInfo> tree; // minimum info of missing values
int base;
//Max2D const* maximum;
MinInfo getTree(int left, int right) const{
auto const oldLeft=left, oldRight=right;
MinInfo result{0, INT_MAX};
left+=int(tree.size()/2); right+=int(tree.size()/2);
for(;left<right; left>>=1, right>>=1){
if(left&1) result=result+tree[left++];
if(right&1) result=result+tree[--right];
}
assert(([&]{
MinInfo naive{0, INT_MAX};
for(int index=oldLeft; index<oldRight; ++index){
naive=naive+tree[index+int(tree.size()/2)];
assert(tree[index+int(tree.size()/2)].count==1);
assert(tree[index+int(tree.size()/2)].value==cover[index].cover.missing);
}
assert(naive.count==result.count);
assert(naive.value==result.value);
return true;
}()));
return result;
}
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}, 0});
for(int index=1; index<number; ++index){
auto& [curCover, curCoverIndex]=cover.back();
auto& [prevBound, prevMissing]=curCover;
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;
++curCoverIndex;
assert(curCoverIndex==index);
}else{
cover.push_back({{next, prevMissing+diff-1}, index});
}
}
/*
suffix.resize(cover.size());
suffix.back()={1, cover.back().cover.missing};
for(int pos=(int)cover.size()-1; pos--;)
suffix[pos]=suffix[pos+1]+cover[pos].cover.missing;
*/
tree.resize(cover.size()*2);
for(int index=0; index<(int)cover.size(); ++index)
tree[cover.size()+index]={1, cover[index].cover.missing};
for(auto index=(int)cover.size(); --index;)
tree[index]=tree[index*2]+tree[index*2+1];
}
void setWithoutBuild(int index, Pos pos){
assert(index<number);
items[index]=pos;
}
int get_(Cover const previous, Max2D const& maximum)const{
auto const countNaive=[&](int left, int right){
int result{};
for(int pos1=left; pos1<right; ++pos1)
result+=(previous+cover[pos1].cover).missing==0;
return result;
};
// return countNaive(0,(int)cover.size());
int result=0;
int pos=0;
auto const advanceUnion=[&]{
// advance pos to first that covers the whole of the union area (target)
assert(pos>=0);
if(pos==(int)cover.size()) return;
auto const oldPos=pos;
auto const target=cover[pos].cover.bound+previous.bound;
auto const value=maximum.get(target.minimum.row, target.maximum.row, target.minimum.col, target.maximum.col)-base;
assert(cover[pos].index<=value);
--pos;
for(int step=1<<(31^__builtin_clz((int)cover.size())); step; step>>=1)
if(pos+step<(int)cover.size() and cover[pos+step].index<value)
pos+=step;
assert(pos<oldPos or cover[pos].index<value);
++pos;
if(pos!=(int)cover.size()){
assert(cover[pos].index>=value);
assert(cover[pos].cover.count()+previous.count()>=target.area());
}
assert(pos>=oldPos);
assert(countNaive(oldPos, pos)==0);
};
auto const advanceOnce=[&]{
assert(pos>=0);
if(pos==(int)cover.size()) return;
result+=countNaive(pos, pos+1);
++pos;
};
auto const advanceSameIntersect=[&](int next){
// process the set with the same intersect
assert(pos>=0);
if(pos==(int)cover.size()) return;
int const oldPos=pos;
auto const curIntersect=cover[pos].cover.bound.intersectUnchecked(previous.bound);
assert(curIntersect.valid());
/*
for(int step=1<<(31^__builtin_clz((int)cover.size())); step; step>>=1)
if(pos+step<(int)cover.size()){
auto const tmp=cover[pos+step].cover.bound.intersectUnchecked(previous.bound);
assert(tmp.valid());
assert(tmp.contains(curIntersect));
if(tmp.area()==curIntersect.area())
pos+=step;
}
++pos;
*/
pos=next;
assert(pos>=0); assert(pos<=(int)cover.size());
assert(pos>=oldPos);
auto const [minCount, minMissing]=getTree(oldPos, pos);
assert(minMissing>=curIntersect.area()-previous.missing);
int curResult=0;
if(minMissing==curIntersect.area()-previous.missing) curResult=minCount;
result+=curResult;
assert(([&]{
auto const naive=countNaive(oldPos, pos);
assert(naive==curResult);
return true;
}()));
assert(pos>=oldPos);
if(pos!=(int)cover.size())
assert(cover[pos].cover.bound.intersectUnchecked(previous.bound).area()>curIntersect.area());
};
advanceUnion();
advanceOnce();
if(pos==(int)cover.size()) return result;
assert(not previous.bound.contains(cover[pos].cover.bound));
advanceUnion();
if(pos==(int)cover.size()) return result;
if(not cover[pos].cover.bound.contains(previous.bound)){
auto const countExceed=[&](int pos)->int{
return
(cover[pos].cover.bound.minimum.row<previous.bound.minimum.row)+
(cover[pos].cover.bound.minimum.col<previous.bound.minimum.col)+
(cover[pos].cover.bound.maximum.row>previous.bound.maximum.row)+
(cover[pos].cover.bound.maximum.col>previous.bound.maximum.col);
};
assert(countExceed(pos)==1);
int next=pos;
for(int step=1<<(31^__builtin_clz((int)cover.size())); step; step>>=1)
if(next+step<(int)cover.size() and countExceed(next)==1)
next+=step;
assert(countExceed(pos)==countExceed(next));
advanceSameIntersect(next+1);
if(pos==(int)cover.size()) return result;
}
assert(cover[pos].cover.bound.contains(previous.bound));
advanceSameIntersect((int)cover.size());
assert(pos==(int)cover.size());
return result;
}
std::pair<int, Cover> get(Cover const previous, Max2D const& maximum)const{
return {get_(previous, maximum), previous+cover.back().cover};
}
};
int number;
std::vector<Block> data;
Max2D maximum;
MyData(){}
MyData(int const H, int const W, std::vector<int> const& R, std::vector<int> const& C):
number(H*W), data((number-1)/blockSize+1), maximum(H, W)
{
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 blockIndex=0; blockIndex<(int)data.size(); ++blockIndex)
for(int indexInBlock=0; indexInBlock<data[blockIndex].number; ++indexInBlock){
auto const index=blockIndex*blockSize+indexInBlock;
auto const row=R[index], col=C[index];
data[blockIndex].items[indexInBlock]={row, col};
assert(maximum.get(row, col)==0);
maximum.set(row, col, index);
}
for(int index=0; index<(int)data.size(); ++index){
//data[index].maximum=&maximum;
data[index].base=index*blockSize;
buildAt(index);
}
}
void buildAt(int index){
data[index].build(
//index*blockSize, maximum
);
}
int getResult() const{
Cover current{Rectangle::from(data[0].items[0]), 1};
int result{};
for(auto const& it: data){
auto [count, next]=it.get(current, maximum);
result+=count; current=next;
}
assert(current.missing==0);
if(result<=0){
assert(std::cerr<<"result="<<result<<'\n');
assert(false);
}
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);
assert(maximum.get(x.row, x.col)==first);
assert(maximum.get(y.row, y.col)==sec);
maximum.set(x.row, x.col, sec);
maximum.set(y.row, y.col, first);
buildAt(first/blockSize);
if(first/blockSize!=sec/blockSize)
buildAt(sec/blockSize);
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);
}
