#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define sz(A) (int)(A.size())
#define pi pair<int, int>
#define f first
#define s second
#define eb emplace_back
#define pb push_back
#define ll long long
#define V vector
const int maxn=2507, base=(1<<12), inf=1e9;
struct Blok {
int lx, px, gy, dy;
};
V<Blok> bloki;
int n, m;
int A[maxn][maxn];
int gora[maxn][maxn], dol[maxn][maxn];
set<pi> przedzialy[maxn];
struct MinSegTree {
int T[2*base];
int query(int a, int b) {
a+=base-1;
b+=base+1;
int minv=inf;
while(a/2!=b/2) {
if(a%2==0) minv=min(minv, T[a+1]);
if(b%2==1) minv=min(minv, T[b-1]);
a/=2; b/=2;
}
return minv;
}
} DolSeg[maxn];
struct MaxSegTree {
int T[2*base];
int query(int a, int b) {
a+=base-1;
b+=base+1;
int maxv=-inf;
while(a/2!=b/2) {
if(a%2==0) maxv=max(maxv, T[a+1]);
if(b%2==1) maxv=max(maxv, T[b-1]);
a/=2; b/=2;
}
return maxv;
}
} GoraSeg[maxn];
struct SumSegTree {
int T[2*base];
void update(int v, int x) {
v+=base;
T[v]=x;
v/=2;
while(v>=1) {
T[v]=T[2*v]+T[2*v+1];
v/=2;
}
}
int query(int a, int b) {
a+=base-1;
b+=base+1;
int sum=0;
while(a/2!=b/2) {
if(a%2==0) sum+=T[a+1];
if(b%2==1) sum+=T[b-1];
a/=2; b/=2;
}
return sum;
}
} SumSeg;
void generuj_gora_dol() {
FOR(j, 1, m) {
{
stack<pi> stosik;
FOR(i, 1, n) {
pi x = {A[i][j], i};
while(!stosik.empty() && stosik.top().f<x.f) stosik.pop();
if(stosik.empty()) {
gora[i][j]=-inf;
stosik.push(x);
continue;
}
gora[i][j]=stosik.top().s;
stosik.push(x);
}
}
{
stack<pi> stosik;
for(int i=n; i>=1; --i) {
pi x = {A[i][j], i};
while(!stosik.empty() && stosik.top().f<x.f) stosik.pop();
if(stosik.empty()) {
dol[i][j]=inf;
stosik.push(x);
continue;
}
dol[i][j]=stosik.top().s;
stosik.push(x);
}
}
}
}
void postaw_przedzialowce() {
FOR(i, 1, n) {
FOR(j, 0, 2*base-1) {
GoraSeg[i].T[j]=-inf;
DolSeg[i].T[j]=inf;
}
FOR(j, 1, m) {
GoraSeg[i].T[j+base]=gora[i][j];
DolSeg[i].T[j+base]=dol[i][j];
}
for(int j=base-1; j>=1; --j) {
GoraSeg[i].T[j]=max(GoraSeg[i].T[2*j], GoraSeg[i].T[2*j+1]);
DolSeg[i].T[j]=min(DolSeg[i].T[2*j], DolSeg[i].T[2*j+1]);
}
}
}
void znajdz_przedzialy_kazdemu_wierszowi() {
FOR(i, 2, n-1) {
{
stack<int> stosik;
FOR(j, 1, m) {
while(!stosik.empty() && A[i][stosik.top()]<A[i][j]) stosik.pop();
if(stosik.empty()) {
stosik.push(j);
continue;
}
int lewo = stosik.top();
stosik.push(j);
if(lewo+1<=j-1) przedzialy[i].insert({lewo+1, j-1});
}
}
{
stack<int> stosik;
for(int j=m; j>=1; --j) {
while(!stosik.empty() && A[i][stosik.top()]<A[i][j]) stosik.pop();
if(stosik.empty()) {
stosik.push(j);
continue;
}
int prawo = stosik.top();
stosik.push(j);
if(j+1<=prawo-1) przedzialy[i].insert({j+1, prawo-1});
}
}
}
}
void znajdz_bloki() {
FOR(i, 2, n-1) {
for(auto &[a, b] : przedzialy[i]) {
FOR(j, i+1, n) {
if(przedzialy[j].find({a, b})==przedzialy[j].end()) {
bloki.pb({a, b, i, j-1});
break;
}
przedzialy[j].erase({a, b});
}
}
}
}
V<int> kub[maxn];
int rozw_blok(Blok &blok) {
// cout << "blok: " << blok.lx << ' ' << blok.px << ' ' << blok.gy << ' ' << blok.dy << '\n';
int sum=0;
FOR(i, blok.gy, blok.dy) {
for(int idx_do_wywalenia : kub[i]) SumSeg.update(idx_do_wywalenia, 0);
kub[i].clear();
int indexgorny = GoraSeg[i+1].query(blok.lx, blok.px);
int indexdolny = DolSeg[i-1].query(blok.lx, blok.px);
if(indexdolny>=i+1) {
SumSeg.update(i, 1);
if(indexdolny>blok.dy) kub[0].eb(i);
else kub[indexdolny].eb(i);
}
if(indexgorny!=-inf) sum+=SumSeg.query(indexgorny+1, i);
else sum+=SumSeg.query(0, i);
}
for(int idx_do_wywalenia : kub[0]) SumSeg.update(idx_do_wywalenia, 0);
kub[0].clear();
return sum;
}
int main() {
cin.tie(0) -> ios_base::sync_with_stdio(0);
cin >> n >> m;
FOR(i, 1, n) FOR(j, 1, m) cin>>A[i][j];
generuj_gora_dol();
postaw_przedzialowce();
znajdz_przedzialy_kazdemu_wierszowi();
znajdz_bloki();
int res=0;
for(Blok &blok : bloki) res+=rozw_blok(blok);
cout << res << '\n';
}
Compilation message
/usr/bin/ld: /tmp/ccjiy9mg.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3yZQ5g.o:rect.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccjiy9mg.o: in function `main':
grader.cpp:(.text.startup+0x6fa): undefined reference to `count_rectangles(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'
collect2: error: ld returned 1 exit status
