// moreflags=grader.cpp
// ...
// some simple optimization.
// (it's convenient to have the test cases downloadable.)
// std::map is so slow that I use std::vector instead.
#include "seats.h"
#include<vector>
#include<climits>
#include<algorithm>
#if LOCAL
#include<iostream>
#else
#define NDEBUG
#endif
#include<cassert>
struct Tree{
struct T{
int minimum, count;
T operator+(int lazy) const{return {minimum+lazy, count};}
T operator+(T other) const{
if(minimum<other.minimum) return *this;
if(minimum>other.minimum) return other;
return {minimum, count+other.count};
}
};
struct Node{
int lazy;
T data_;
T data() const{return data_+lazy;}
};
std::vector<Node> data;
Tree(){}
Tree(int number): data(number*2, {0, {0, 1}}){
for(int node=number; --node;)
data[node].data_.count= data[node*2].data_.count+ data[node*2+1].data_.count;
}
// #fixed# note: initial state is inconsistent (counts values of nonleafs are 1)
// (I knew that this will be problematic later...)
void add(int left, int right, int value){
if(left==right) return;
assert(left<right);
left+=int(data.size()/2); right+=int(data.size()/2);
std::array<int, 2> const old{{left, right-1}};
for(; left<right; left>>=1, right>>=1){
if(left&1) data[left++].lazy+=value;
if(right&1) data[--right].lazy+=value;
}
for(auto it: old){
for(it>>=1; it; it>>=1){
data[it].data_=data[it*2].data()+data[it*2+1].data();
}
}
}
/* // not necessary (...)
void get(int left, int right){
assert(left<right);
left+=int(data.size()/2); right+=int(data.size()/2);
for(auto it: {left, right-1}){
for(int shift=31^__builtin_clz(it); shift; --shift){
auto const node=it>>shift;
if(auto const l=data[node].lazy){
data[node].lazy=0;
data[node].data_.minimum+=l;
data[node*2].lazy+=l;
data[node*2+1].lazy+=l;
}
}
}
T result{};
}
*/
int get(){
// operator+ is commutative
auto const d=data[1].data();
assert(d.minimum>=4);
return d.minimum==4 ? d.count: 0;
}
};
struct MyData{
MyData(){}
//int width;
std::vector<std::vector<int>> value; // pos -> time (in 0..H*W), with padded (H*W) values
struct Pos{ int row, col; };
std::vector<Pos> pos; // time -> pos
Tree tree;
template<int factor> void addTree(std::vector<std::pair<int, int>>& delta, Pos minimum){
// instead of adding to the tree, update the delta map.
// delta[a]=b -> tree.add(a, (int)pos.size(), b);
auto const [r, c]=minimum;
std::array<int, 4> times{{
value[r][c],
value[r+1][c],
value[r][c+1],
value[r+1][c+1],
}};
std::sort(begin(times), end(times));
delta.push_back({times[0], factor});
delta.push_back({times[1], -factor});
delta.push_back({times[2], factor*5});
delta.push_back({times[3], -factor*5});
/*
tree.add(times[0], int(tree.data.size()/2), factor);
tree.add(times[1], int(tree.data.size()/2), -factor);
tree.add(times[2], int(tree.data.size()/2), factor*5);
tree.add(times[3], int(tree.data.size()/2), -factor*5);
*/
// 5 is always greater than 4 => impossible
}
void applyMap(std::vector<std::pair<int, int>> delta){
std::sort(begin(delta), end(delta), [&](auto const& first, auto const& sec){
return first.first<sec.first;
});
for(int index=0, curDelta=0; index<(int)delta.size(); ++index){
curDelta+=delta[index].second;
if(index==(int)delta.size()-1 or delta[index].first!=delta[index+1].first){
if(curDelta!=0){
tree.add(delta[index].first, int(tree.data.size()/2), curDelta);
curDelta=0;
}
}
}
}
MyData(int const H, int const W, std::vector<int> const& R_, std::vector<int> const& C_):
value(H+2, std::vector<int>(W+2, H*W)),
pos(H*W), tree(H*W)
{
for(int time=0; time<H*W; ++time){
pos[time]={R_[time], C_[time]};
value[R_[time]+1][C_[time]+1]=time;
}
std::vector<std::pair<int, int>> delta;
for(int i=0; i<(int)value.size()-1; ++i)
for(int j=0; j<(int)value[0].size()-1; ++j){
addTree<1>(delta, {i, j});
//applyMap(std::move(delta)); delta.clear();
}
applyMap(std::move(delta));
}
int swap(int first, int sec){
std::swap(pos[first], pos[sec]);
std::array<std::array<int, 2> /* can be Pos too if it has comparison operators */, 8> minimums{{
{pos[first].row, pos[first].col},
{pos[first].row, pos[first].col+1},
{pos[first].row+1, pos[first].col},
{pos[first].row+1, pos[first].col+1},
{pos[sec].row, pos[sec].col},
{pos[sec].row, pos[sec].col+1},
{pos[sec].row+1, pos[sec].col},
{pos[sec].row+1, pos[sec].col+1},
}};
std::sort(begin(minimums), end(minimums));
auto const last=std::unique(begin(minimums), end(minimums));
std::vector<std::pair<int, int>> delta;
std::for_each(minimums.begin(), last, [&](auto it){
addTree<-1>(delta, {it[0], it[1]});
});
value[pos[first].row+1][pos[first].col+1]=first;
value[pos[sec].row+1][pos[sec].col+1]=sec;
std::for_each(minimums.begin(), last, [&](auto it){
addTree<1>(delta, {it[0], it[1]});
});
applyMap(std::move(delta));
return tree.get();
}
} myData;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
myData=MyData{H, W, std::move(R), std::move(C)};
}
int swap_seats(int a, int b) {
return myData.swap(a, b);
}
