Submission #298489

#	Time	Username	Problem	Language	Result	Execution time	Memory
298489		daniel920712	Rectangles (IOI19_rect)	C++14	50 / 100	922 ms	255096 KiB

rect

#include "rect.h"
#include <stdio.h>

using namespace std;
int can1[205][205][205]={0};
int can2[205][205][205]={0};
bool have[2505][2505]={0};
int N,M;
int l,r,u,d,con;
vector< vector<int> > tt;
void F(int x,int y)
{
    if(x<0||y<0||x>=N||y>=M||tt[x][y]||have[x][y]) return;
    have[x][y]=1;
    con++;
    l=min(l,y);
    r=max(r,y);
    u=min(u,x);
    d=max(d,x);
    F(x,y+1);
    F(x,y-1);
    F(x+1,y);
    F(x-1,y);
}
long long count_rectangles(vector< vector<int> > all)
{
    int i,j,k,m,n,big=0,ok;
    long long ans=0;
    N=all.size();
    M=all[0].size();
    tt=all;
    if(N==3)
    {
        for(i=1;i<M-1;i++)
        {
            ok=1;
            big=0;
            for(j=i;j<M-1;j++)
            {
                if(all[1][j]>=all[0][j]||all[1][j]>=all[2][j]) ok=0;
                big=max(big,all[1][j]);
                if(ok&&big<min(all[1][i-1],all[1][j+1])) ans++;
            }
        }
        return ans;
    }
    else if(N<3) return 0;
    else if(max(N,M)<=200)
    {
        for(i=1;i<N;i++)
        {
            for(j=1;j<M;j++)
            {
                big=0;
                for(k=j;k<M-1;k++)
                {
                    big=max(big,all[i][k]);
                    if(big<all[i][j-1]&&big<all[i][k+1]) can1[i][j][k]=1;
                    can1[i][j][k]+=can1[i-1][j][k];
                }
            }
        }
        for(i=1;i<M;i++)
        {
            for(j=1;j<N;j++)
            {
                big=0;
                for(k=j;k<N-1;k++)
                {
                    big=max(big,all[k][i]);
                    if(big<all[j-1][i]&&big<all[k+1][i]) can2[i][j][k]=1;
                    can2[i][j][k]+=can2[i-1][j][k];
                }
            }
        }
        for(i=1;i<N-1;i++)
        {
            for(j=i;j<N-1;j++)
            {
                for(k=1;k<M-1;k++)
                {
                    for(l=k;l<M-1;l++)
                    {

                        if(can1[j][k][l]-can1[i-1][k][l]==j-i+1&&can2[l][i][j]-can2[k-1][i][j]==l-k+1) ans++;

                    }
                }
            }
        }
        //printf("%lld\n",ans);
    }
    else
    {
        ans=0;
        for(i=0;i<N;i++)
        {
            for(j=0;j<M;j++)
            {
                con=0;
                u=1e9;
                d=0;
                l=1e9;
                r=0;
                if(!have[i][j]&&all[i][j]==0)
                {
                    F(i,j);
                    //printf("%d %d %d %d %d\n",l,r,u,d,con);
                    if((r-l+1)*(d-u+1)==con&&l!=0&&r!=M-1&&u!=0&&d!=N-1) ans++;
                }
            }
        }
        //printf("%lld\n",ans);
        //while(1) ans=ans;
    }
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:27:15: warning: unused variable 'm' [-Wunused-variable]
   27 |     int i,j,k,m,n,big=0,ok;
      |               ^
rect.cpp:27:17: warning: unused variable 'n' [-Wunused-variable]
   27 |     int i,j,k,m,n,big=0,ok;
      |                 ^

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