This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
#include "rect.h"
vector<vector<int>> it;
vector<int> x={1,-1,0,0};
vector<int> y={0,0,-1,1};
int vis[2501][2501];
int n,m;
vector<pair<int,int>> comp;
void dfs(int i,int j){
vis[i][j]=1;
comp.pb({i,j});
//<<i<<",,"<<j<<endl;
for(int ii=0;ii<4;ii++){
int xx=i+x[ii];
int yy=j+y[ii];
if(xx<0 or yy<0 or xx>=n or yy>=m){
continue;
}
if(it[xx][yy]==0){
if(vis[xx][yy]==0){
dfs(xx,yy);
}
}
}
}
int val[201][201][201];
int val2[201][201][201];
bool val3[201][201][201][201];
bool val4[201][201][201][201];
llo count_rectangles(vector<vector<int>> ac) {
it=ac;
/*for(auto j:ac){
for(auto i:j){
cout<<i<<".";
}
cout<<endl;
}*/
n=it.size();
m=it[0].size();
if(n<=2 or m<=2){
return 0;
}
if(n==3){
llo co=0;
for(int i=1;i<m-1;i++){
int ma=it[1][i];
for(int j=i;j<m-1;j++){
if(it[1][j]>=min(it[0][j],it[2][j])){
break;
}
ma=max(ma,it[1][j]);
if(ma<min(it[1][i-1],it[1][j+1])){
co+=1;
}
}
}
return co;
}
int stt=1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(it[i][j]>1){
stt=0;
}
}
}
if(stt){
int co=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
comp.clear();
if(it[i][j]==0){
if(vis[i][j]==0){
dfs(i,j);
int mi1=0;
int mi2=n;
int ma1=0;
int ma2=m;
int st=1;
for(auto jj:comp){
mi1=max(mi1,jj.a);
mi2=min(mi2,jj.a);
ma1=max(ma1,jj.b);
ma2=min(ma2,jj.b);
if(jj.a==0 or jj.a==n-1 or jj.b==0 or jj.b==m-1){
st=0;
}
}
if((int)(comp.size())==(mi1-mi2+1)*(ma1-ma2+1)){
co+=st;
// cout<<i<<":"<<j<<endl;
}
}
}
}
}
return co;
}
for(int j=1;j<m-1;j++){
for(int i=1;i<n-1;i++){
int ma=it[i][j];
for(int ii=i;ii<n-1;ii++){
ma=max(ma,it[ii][j]);
if(ma<min(it[i-1][j],it[ii+1][j])){
val[j][i][ii]=1;
}
}
}
}
for(int j=1;j<n-1;j++){
for(int i=1;i<m-1;i++){
int ma=it[j][i];
for(int ii=i;ii<m-1;ii++){
ma=max(ma,it[j][ii]);
if(ma<min(it[j][i-1],it[j][ii+1])){
val2[j][i][ii]=1;
}
}
}
}
for(int j=1;j<m-1;j++){
for(int i=1;i<n-1;i++){
for(int ii=i;ii<n-1;ii++){
for(int jj=j;jj<m-1;jj++){
if(val[jj][i][ii]==0){
break;
}
val3[i][ii][j][jj]=1;
}
}
}
}
llo ans2=0;
for(int j=1;j<n-1;j++){
for(int i=1;i<m-1;i++){
for(int ii=i;ii<m-1;ii++){
for(int jj=j;jj<n-1;jj++){
if(val2[jj][i][ii]==0){
break;
}
val3[i][ii][j][jj]&=1;
ans2+=val3[i][ii][j][jj];
}
}
}
}
return ans2;
}
Compilation message (stderr)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(vterminate.o): In function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1a): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(vterminate.o): In function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x27): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x19): relocation truncated to fit: R_X86_64_32S against symbol `std::ios_base::Init::_S_refcount' defined in .bss._ZNSt8ios_base4Init11_S_refcountE section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x59): 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/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.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/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x6b): 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/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x80): 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/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x8b): 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/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xa0): 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/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xab): 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/9/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(ios_init.o): In function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0xba): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status
