Submission #579227

#	Time	Username	Problem	Language	Result	Execution time	Memory
579227		ogibogi2004	Rectangles (IOI19_rect)	C++14	100 / 100	3729 ms	996748 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
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;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:140:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for(int i=0;i<to_check.size();i++)
      |                 ~^~~~~~~~~~~~~~~~
rect.cpp:169:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         for(int j=0;j<check_row1[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:171:17: warning: unused variable 'x1' [-Wunused-variable]
  171 |             int x1=check_row1[i][j].x1;
      |                 ^~
rect.cpp:193:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |         for(int j=0;j<check_row2[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:196:17: warning: unused variable 'x2' [-Wunused-variable]
  196 |             int x2=check_row2[i][j].x2;
      |                 ^~
rect.cpp:217:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |         for(int i=0;i<check_col1[j].size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:221:17: warning: unused variable 'y1' [-Wunused-variable]
  221 |             int y1=check_col1[j][i].y1;
      |                 ^~
rect.cpp:241:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  241 |         for(int i=0;i<check_col2[j].size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:246:17: warning: unused variable 'y2' [-Wunused-variable]
  246 |             int y2=check_col2[j][i].y2;
      |                 ^~
rect.cpp:256:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  256 |     for(int i=0;i<to_check.size();i++)
      |                 ~^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 28 / 28