| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 579226 | ogibogi2004 | Rectangles (IOI19_rect) | C++14 | 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 "rect.h"
#include<bits/stdc++.h>
const int MAXN=2502;
const int logN=12;
int bigger_up[MAXN][MAXN];
int bigger_down[MAXN][MAXN];
int bigger_left[MAXN][MAXN];
int bigger_right[MAXN][MAXN];
int n,m;
vector<vector<int> >b;
void precomp(int t)
{
for(int i=0;i<n;i++)
{
stack<int>st;
for(int j=0;j<m;j++)
{
while(!st.empty()&&b[i][st.top()]+t<=b[i][j])
{
st.pop();
}
if(!st.empty())
{
bigger_left[i][j]=st.top();
}
else
{
bigger_left[i][j]=-1;
}
st.push(j);
}
}
for(int i=0;i<n;i++)
{
stack<int>st;
for(int j=m-1;j>=0;j--)
{
while(!st.empty()&&b[i][st.top()]+t<=b[i][j])
{
st.pop();
}
if(!st.empty())
{
bigger_right[i][j]=st.top();
}
else
{
bigger_right[i][j]=2*MAXN;
}
st.push(j);
}
}
for(int j=0;j<m;j++)
{
stack<int>st;
for(int i=0;i<n;i++)
{
while(!st.empty()&&b[st.top()][j]+t<=b[i][j])
{
st.pop();
}
if(!st.empty())
{
bigger_up[i][j]=st.top();
}
else
{
bigger_up[i][j]=-1;
}
st.push(i);
}
}
for(int j=0;j<m;j++)
{
stack<int>st;
for(int i=n-1;i>=0;i--)
{
while(!st.empty()&&b[st.top()][j]+t<=b[i][j])
{
st.pop();
}
if(!st.empty())
{
bigger_down[i][j]=st.top();
}
else
{
bigger_down[i][j]=2*MAXN;
}
st.push(i);
}
}
}
struct rect
{
int x1,x2,y1,y2;
int idx;
bool operator<(rect const& other)const
{
if(x1!=other.x1)return x1<other.x1;
if(x2!=other.x2)return x2<other.x2;
if(y1!=other.y1)return y1<other.y1;
return y2<other.y2;
}
};
vector<rect>check_row1[MAXN],check_col1[MAXN];
vector<rect>check_row2[MAXN],check_col2[MAXN];
int cnt[MAXN*MAXN];
int st[MAXN][logN];
int pw2[MAXN];
long long count_rectangles(vector<vector<int> > a) {
b=a;
n=a.size();
m=a[0].size();
precomp(0);
vector<rect>to_check;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(bigger_down[i][j]==-1)continue;
if(bigger_left[i][j]==2*MAXN)continue;
if(bigger_up[i][j]==2*MAXN)continue;
if(bigger_right[i][j]==-1)continue;
int x1=bigger_up[i][j]+1;
int x2=bigger_down[i][j]-1;
int y1=bigger_left[i][j]+1;
int y2=bigger_right[i][j]-1;
if(x1<=0)continue;
if(x2>=n-1)continue;
if(y1<=0)continue;
if(y2>=m-1)continue;
to_check.push_back({x1,x2,y1,y2,0});
}
}
sort(to_check.begin(),to_check.end());
for(int i=0;i<to_check.size();i++)
{
to_check[i].idx=i;
if(i!=0)
{
if(to_check[i].x1==to_check[i-1].x1&&to_check[i].x2==to_check[i-1].x2&&to_check[i].y1==to_check[i-1].y1&&to_check[i].y2==to_check[i-1].y2)continue;
}
check_row1[to_check[i].x1-1].push_back(to_check[i]);
check_row2[to_check[i].x2+1].push_back(to_check[i]);
check_col1[to_check[i].y1-1].push_back(to_check[i]);
check_col2[to_check[i].y2+1].push_back(to_check[i]);
}
int pw=1,c=0;
for(int j=1;j<MAXN;j++)
{
if(pw*2<=j){pw*=2;c++;}
pw2[j]=c;
}
precomp(1);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)st[j][0]=bigger_down[i][j];
for(int step=1;step<logN;step++)
{
for(int j=0;j<m;j++)
{
st[j][step]=min(st[j][step-1],st[min(m-1,j+(1<<(step-1)))][step-1]);
}
}
for(int j=0;j<check_row1[i].size();j++)
{
int x1=check_row1[i][j].x1;
int x2=check_row1[i][j].x2;
int y1=check_row1[i][j].y1;
int y2=check_row1[i][j].y2;
int d=(y2-y1+1);
d=pw2[d];
c=d;
int mxdown=min(st[y1][c],st[y2-(1<<c)+1][c]);
//cout<<check_row1[i][j].idx<<" "<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<" "<<mxdown<<endl;
if(mxdown>x2)cnt[check_row1[i][j].idx]++;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)st[j][0]=bigger_up[i][j];
for(int step=1;step<logN;step++)
{
for(int j=0;j<m;j++)
{
st[j][step]=max(st[j][step-1],st[min(m-1,j+(1<<(step-1)))][step-1]);
}
}
for(int j=0;j<check_row2[i].size();j++)
{
int x1=check_row2[i][j].x1;
int x2=check_row2[i][j].x2;
int y1=check_row2[i][j].y1;
int y2=check_row2[i][j].y2;
int d=(y2-y1+1);
d=pw2[d];
c=d;
int mxup=max(st[y1][c],st[y2-(1<<c)+1][c]);
if(mxup<x1)cnt[check_row2[i][j].idx]++;
}
}
for(int j=0;j<m;j++)
{
for(int i=0;i<n;i++)st[i][0]=bigger_right[i][j];
for(int step=1;step<logN;step++)
{
for(int i=0;i<n;i++)
{
st[i][step]=min(st[i][step-1],st[min(n-1,i+(1<<(step-1)))][step-1]);
}
}
for(int i=0;i<check_col1[j].size();i++)
{
int x1=check_col1[j][i].x1;
int x2=check_col1[j][i].x2;
int y1=check_col1[j][i].y1;
int y2=check_col1[j][i].y2;
int d=(x2-x1+1);
d=pw2[d];
c=d;
int mxright=min(st[x1][c],st[x2-(1<<c)+1][c]);
if(mxright>y2)cnt[check_col1[j][i].idx]++;
}
}
for(int j=0;j<m;j++)
{
for(int i=0;i<n;i++)st[i][0]=bigger_left[i][j];
for(int step=1;step<logN;step++)
{
for(int i=0;i<n;i++)
{
st[i][step]=max(st[i][step-1],st[min(n-1,i+(1<<(step-1)))][step-1]);
}
}
for(int i=0;i<check_col2[j].size();i++)
{
int x1=check_col2[j][i].x1;
int x2=check_col2[j][i].x2;
int y1=check_col2[j][i].y1;
int y2=check_col2[j][i].y2;
int d=(x2-x1+1);
d=pw2[d];
c=d;
int mxleft=max(st[x1][c],st[x2-(1<<c)+1][c]);
if(mxleft<y1)cnt[check_col2[j][i].idx]++;
}
}
int ans=0;
//cout<<"??\n";
for(int i=0;i<to_check.size();i++)
{
//printf("%d %d %d %d\n",to_check[i].x1,to_check[i].x2,to_check[i].y1,to_check[i].y2);
//cerr<<to_check[i].x1<<" "<<to_check[i].x2<<" "<<to_check[i].y1<<" "<<to_check[i].y2<<" "<<cnt[to_check[i].idx]<<" \n";
if(cnt[i]==4)ans++;
}
return ans;
}