| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 571283 | azberjibiou | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
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>
#include "rect.h"
using namespace std;
typedef struct rect{
int x1, x2, y1, y2;
rect() : x1(0), x2(0), y1(0), y2(0) {}
rect(int x1, int x2, int y1, int y2) : x1(x1), x2(x2), y1(y1), y2(y2) {}
}rect;
int N, M;
vector <rect> v;
bool cmp1(rect a, rect b)
{
if(a.x1!=b.x1) return a.x1<b.x1;
if(a.x2!=b.x2) return a.x2<b.x2;
if(a.y1!=b.y1) return a.y1<b.y1;
return a.y2<b.y2;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
N=a.size();
M=a[0].size();
for(int i=1;i<N-1;i++)
{
for(int j=1;j<M-1;j++)
{
int u=i, d=i, l=j, r=j;
while(u!=-1 && a[u][j]<=a[i][j]) u--;
while(d!=N && a[d][j]<=a[i][j]) d++;
while(l!=-1 && a[i][l]<=a[i][j]) l--;
while(r!=M && a[i][r]<=a[i][j]) r++;
if(u!=-1 && d!=N && l!=-1 && r!=M) v.emplace_back(u+1, d-1, l+1, r-1);
}
}
sort(v.begin(), v.end(), cmp1);
v.erase(unique(v.begin(), v.end()), v.end());
int ans=0;
for(auto ele : v)
{
bool ok=true;
for(int i=ele.x1;i<=ele.x2;i++)
{
for(int j=ele.y1;j<=ele.y2;j++)
{
if(a[ele.x1-1][j]<=a[i][j] || a[ele.x2+1][j]<=a[i][j] || a[i][ele.y1-1]<=a[i][j] || a[i][ele.y2+1]<=a[i][j])
ok=false;
}
}
if(ok) ans++;
}
return ans;
}