#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 1e9 + 10;
const int maxn = 2500 + 10;
const int logn = 13;
struct Node{
int l, r, u, d; Node( int l = -inf, int r = inf, int u = -inf, int d = inf ) : l(l), r(r), u(u), d(d) {}
Node operator + ( Node n ){
return Node( min( l, n.l ), max( r, n.r ), min( u, n.u ), max( d, n.d ) );
}
};
Node dp[logn][logn][maxn][maxn];
int l[maxn][maxn], r[maxn][maxn], u[maxn][maxn], d[maxn][maxn];
long long count_rectangles( vector<vector<int>> mat ) {
int n = mat.size(), m = mat[0].size();
for( int i = 0; i < n; i++ ){
stack<pair<int, pair<int, int>>> pilha;
pilha.push({ inf, make_pair(-1, -1) });
for( int j = 0; j < m; j++ ){
l[i][j] = -1; r[i][j] = m;
while( pilha.top().first < mat[i][j] ){
auto [a, b] = pilha.top().second;
r[a][b] = j;
pilha.pop();
}
auto [a, b] = pilha.top().second;
l[i][j] = (( pilha.top().first == mat[i][j] ) ? l[a][b] : b );
pilha.push({ mat[i][j], make_pair( i, j ) });
}
}
for( int j = 0; j < m; j++ ){
stack<pair<int, pair<int, int>>> pilha;
pilha.push({ inf, make_pair(-1, -1) });
for( int i = 0; i < n; i++ ){
u[i][j] = -1; d[i][j] = n;
while( pilha.top().first < mat[i][j] ){
auto [a, b] = pilha.top().second;
d[a][b] = i;
pilha.pop();
}
auto [a, b] = pilha.top().second;
u[i][j] = (( pilha.top().first == mat[i][j] ) ? u[a][b] : a );
pilha.push({ mat[i][j], make_pair( i, j ) });
}
}
for( int ki = 0; ki < logn; ki++ )
for( int kj = 0; kj < logn; kj++ )
for( int i = 0; i < n; i++ )
for( int j = 0; j < m; j++ ){
if( ki == 0 && kj == 0) dp[0][0][i][j] = Node( l[i][j], r[i][j], u[i][j], d[i][j] );
else if( ki == 0 ){
if( j + (1<<kj) <= m ) dp[ki][kj][i][j] = dp[ki][kj - 1][i][j] + dp[ki][kj - 1][i][j + (1<<(kj - 1))];
}
else if( i + (1<<ki) <= n ) dp[ki][kj][i][j] = dp[ki - 1][kj][i][j] + dp[ki - 1][kj][i + (1<<(ki - 1))][j];
}
auto query = [&]( int i1, int j1, int i2, int j2 ){
int ki = 31 - __builtin_clz(i2 - i1 + 1), kj = 31 - __builtin_clz(j2 - j1 + 1);
return dp[ki][kj][i1][j1] + dp[ki][kj][i1][j2 - (1<<kj) + 1] + dp[ki][kj][i2 - (1<<ki) + 1][j1] + dp[ki][kj][i2 - (1<<ki) + 1][j2 - (1<<kj) + 1];
};
ll resp = 0;
Node x = query( 1, 1, 1, 1 );
set<tuple<int, int, int, int>> s;
for( int i = 1; i < n - 1; i++ )
for( int j = 1; j < m - 1; j++ ){
if( l[i][j] == -1 || r[i][j] == m || u[i][j] == -1 || d[i][j] == n ) continue;
Node x = query( u[i][j] + 1, l[i][j] + 1, d[i][j] - 1, r[i][j] - 1 );
if( x.u < u[i][j] || x.l < l[i][j] || x.d > d[i][j] || x.r > r[i][j] ) continue;
s.insert(make_tuple( l[i][j], r[i][j], u[i][j], d[i][j] ) );
}
if( resp > n*m ) return 0;
return s.size();
}
Compilation message (stderr)
/tmp/ccUD4eu5.o: in function `_GLOBAL__sub_I_dp':
rect.cpp:(.text.startup+0x8): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x72): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x87): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x92): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xa7): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xb2): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xc1): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
collect2: error: ld returned 1 exit status
