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 "rect.h"
#include<bits/stdc++.h>
using namespace std;
long long count_rectangles(vector<vector<int> > a)
{
int n=a.size();
int m=a[0].size();
int i, j, k, l;
long long ans=0;
vector<pair<int, int> >v[2510];
map<pair<int, int>, vector<int> >mp;
for(i=1;i<n-1;i++)
{
for(j=0;j<m;j++)
{
l=-1;
for(k=j+1;k<m;k++)
{
if(k>j+1)
{
if(a[i][j]>l&&a[i][k]>l)
{
v[i].push_back({j, k});
}
}
l=max(l, a[i][k]);
}
}
}
for(j=1;j<m-1;j++)
{
for(i=0;i<n;i++)
{
l=-1;
for(k=i+1;k<n;k++)
{
if(k>i+1)
{
if(a[i][j]>l&&a[k][j]>l)
{
mp[{i, k}].push_back(j);
}
}
l=max(l, a[k][j]);
}
}
}
for(i=1;i<n-1;i++)
{
for(j=i;j<n-1;j++)
{
if(mp.find({i-1, j+1})==mp.end())continue;
vector<int>V=mp[{i-1, j+1}];
int A[2510]={};
for(k=0;k<V.size();k++)A[V[k]]++;
for(k=1;k<m;k++)
{
A[k]+=A[k-1];
}
map<pair<int, int>, int>mp2;
for(k=i;k<=j;k++)
{
for(l=0;l<v[k].size();l++)
{
mp2[v[k][l]]++;
}
}
map<pair<int, int>, int>::iterator it;
for(it=mp2.begin();it!=mp2.end();it++)
{
if(it->second==j-i+1)
{
if(A[it->first.second-1]-A[it->first.first]==it->first.second-1-it->first.first)ans++;
}
}
}
}
return ans;
}
Compilation message (stderr)
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(k=0;k<V.size();k++)A[V[k]]++;
| ~^~~~~~~~~
rect.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(l=0;l<v[k].size();l++)
| ~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |