// moreflags=grader.cpp
// 13
//
// reverted to submission 286053 .
#include "rect.h"
#include<vector>
#include<set>
#include<algorithm>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<climits>
long long count_rectangles(std::vector<std::vector<int> > a) {
if(a.size()<3 or a[0].size()<3) return 0;
struct Set{
using Node=std::array<int, 2>;
std::vector<Node> data;
static Node merge(Node first, Node sec){
return {{std::min(first[0], sec[0]), std::max(first[1], sec[1])}};
}
Set(int number): data(number*2, {{INT_MAX, INT_MIN}}){}
void add(int index){
auto node=index+(int)data.size()/2;
data[node]={index, index};
for(node>>=1; node; node>>=1) data[node]=merge(data[node*2], data[node*2+1]);
}
Node get(int first, int sec)const{
Node result{{INT_MAX, INT_MIN}};
first+=(int)data.size()/2;
sec+=(int)data.size()/2;
for(; first<sec; first>>=1, sec>>=1){
if(first&1) result=merge(result, data[first++]);
if(sec&1) result=merge(result, data[--sec]);
}
return result;
} // good enough.
};
struct T{ int right, depth; };
using Segments=std::vector<std::vector<T>>;
auto const getSegments=[&](std::vector<int> const& data)->Segments{
Segments result(data.size()-1); // [l] -> list of valid r in reverse sorted order
struct Item{int value, index;};
std::vector<Item> items(data.size());
for(int index=0; index<(int)items.size(); ++index)
items[index]={data[index], index};
std::sort(begin(items), end(items),[&](Item first, Item sec){return first.value>sec.value;});
Set done((int)items.size());
for(auto [value, index]: items){
done.add(index);
auto const next=done.get(index+1, (int)items.size())[0];
auto const prev=done.get(0, index)[1];
if(prev!=INT_MIN and next!=INT_MAX){
assert(prev<index); assert(index<next);
if(value<data[prev] and value<data[next]){
result[prev+1].push_back(T{next, 1});
}
}
}
for(auto& it: result)
assert(std::is_sorted(begin(it), end(it), [&](T first, T sec){return first.right>sec.right;}));
return result;
};
std::vector<Segments> rows(a.size()-1), cols(a[0].size()-1);
for(int row=1; row<(int)a.size()-1; ++row)
rows[row]=getSegments(a[row]);
{
std::vector<int> tmp(a.size());
for(int col=1; col<(int)a[0].size()-1; ++col){
std::transform(begin(a), end(a), tmp.begin(),[&](std::vector<int> const& it){return it[col];});
cols[col]=getSegments(tmp);
}
}
auto const computeDepth=[&](std::vector<Segments>& data)->void{
if(data.size()<=2) return;
assert(data[0].empty()); // this is confusing.
for(int row=(int)data.size()-1; --row;){
for(int left=0; left<(int)data[row].size(); ++left){
auto const& v=data[row+1][left];
for(auto& [right, depth]: data[row][left]){
assert(depth==1);
auto const iterator=std::upper_bound(begin(v), end(v), right,
[&](int right, T item){ return item.right<=right; });
if(iterator!=v.end() and iterator->right==right)
depth=iterator->depth+1;
else{
assert(iterator==v.end() or iterator->right<right);
assert(iterator==v.begin() or iterator->right>right);
assert(std::is_sorted(begin(v), end(v), [&](T first, T sec){return first.right>sec.right;}));
}
}
}
}
};
computeDepth(rows);
computeDepth(cols);
struct Bit{
std::vector<int> data;
Bit(int number): data(number){}
void add(int index, int value){
for(; index>=0; index=(index&(index+1))-1)
data[index]+=value;
}
int sumSuffix(int index) const{
int result{};
for(; index<(int)data.size(); index|=index+1)
result+=data[index];
return result;
}
};
Bit bit((int)a[0].size()-1);
enum class EventType{ add, get };
struct Event{ EventType type; int x, y;
bool operator<(Event other) const{return std::tie(y, type)<std::tie(other.y, other.type);}
};
std::vector<Event> events;
int64_t result{};
for(int up=1; up<(int)a.size()-1; ++up)
for(int left=1; left<(int)a[0].size()-1; ++left){
events.clear();
for(auto [right, depthDown]: rows[up][left])
events.push_back({EventType::get, right-left, depthDown});
for(auto [down, depthRight]: cols[left][up])
events.push_back({EventType::add, depthRight, down-up});
std::sort(begin(events), end(events));
for(auto [type, x, y]: events)
if(type==EventType::add){
bit.add(x, 1);
}else{
result+=bit.sumSuffix(x);
}
for(auto [type, x, y]: events)
if(type==EventType::add){
bit.add(x, -1);
}
}
return result;
}
