제출 #298825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
298825		daniel920712	Rectangles (IOI19_rect)	C++14	37 / 100	749 ms	252968 KiB

rect

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

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[2505][2505];
int r[2505][2505];
int u[2505][2505];
int d[2505][2505];
int con[2505][2505]={0};

vector< vector<int> > tt;
vector < pair < int , int > > sa;
set < pair < pair < int , int > , pair < int ,int > > > can;
struct A
{
    int x,y;
    int con;
}how[2505*2505];
void F(int x,int y,int sx,int sy)
{
    if(have[x][y]) return ;
    if(tt[x][y]==tt[sx][sy]) sa.push_back(make_pair(sx,sy));
    have[x][y]=1;
    con[x][y]++;
    l[x][y]=y;
    r[x][y]=y;
    u[x][y]=x;
    d[x][y]=x;
    if(y+1!=M&&(tt[x][y]>tt[x][y+1]||tt[x][y]==tt[x][y+1]&&!have[x][y+1]))
    {
        F(x,y+1,sx,sy);
        l[x][y]=min(l[x][y],l[x][y+1]);
        r[x][y]=max(r[x][y],r[x][y+1]);
        u[x][y]=min(u[x][y],u[x][y+1]);
        d[x][y]=max(d[x][y],d[x][y+1]);
        con[x][y]+=con[x][y+1];
    }
    if(y-1!=0&&(tt[x][y]>tt[x][y-1]||tt[x][y]==tt[x][y-1]&&!have[x][y-1]))
    {
        F(x,y-1,sx,sy);
        l[x][y]=min(l[x][y],l[x][y-1]);
        r[x][y]=max(r[x][y],r[x][y-1]);
        u[x][y]=min(u[x][y],u[x][y-1]);
        d[x][y]=max(d[x][y],d[x][y-1]);
        con[x][y]+=con[x][y-1];
    }
    if(x+1!=N&&(tt[x][y]>tt[x+1][y]||tt[x][y]==tt[x+1][y]&&!have[x+1][y]))
    {
        F(x+1,y,sx,sy);
        l[x][y]=min(l[x][y],l[x+1][y]);
        r[x][y]=max(r[x][y],r[x+1][y]);
        u[x][y]=min(u[x][y],u[x+1][y]);
        d[x][y]=max(d[x][y],d[x+1][y]);
        con[x][y]+=con[x+1][y];
    }
    if(x-1!=0&&(tt[x][y]>tt[x-1][y]||tt[x][y]==tt[x-1][y]&&!have[x-1][y]))
    {
        F(x-1,y,sx,sy);
        l[x][y]=min(l[x][y],l[x-1][y]);
        r[x][y]=max(r[x][y],r[x-1][y]);
        u[x][y]=min(u[x][y],u[x-1][y]);
        d[x][y]=max(d[x][y],d[x-1][y]);
        con[x][y]+=con[x-1][y];
    }
}
bool cmp(A a,A b)
{
    return a.con<b.con;
}
long long count_rectangles(vector< vector<int> > all)
{
    int i,j,k,ll,m,n,big=0,ok,now=0;
    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(ll=k;ll<M-1;ll++)
                    {

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

                    }
                }
            }
        }
    }
    else
    {
        for(i=0;i<N;i++)
        {
            for(j=0;j<M;j++)
            {
                how[now].x=i;
                how[now].y=j;
                now++;
            }
        }
        sort(how,how+N*M,cmp);
        for(i=0;i<N*M;i++)
        {
            if(!have[how[i].x][how[i].y])
            {
                sa.clear();
                F(how[i].x,how[i].y,how[i].x,how[i].y);
                for(auto j:sa)
                {
                    l[j.first][j.second]=l[how[i].x][how[i].y];
                    r[j.first][j.second]=r[how[i].x][how[i].y];
                    u[j.first][j.second]=u[how[i].x][how[i].y];
                    d[j.first][j.second]=d[how[i].x][how[i].y];
                    con[j.first][j.second]=con[how[i].x][how[i].y];
                }
            }
        }
        for(i=0;i<N;i++)
        {
            for(j=0;j<M;j++)
            {
                if((r[i][j]-l[i][j]+1)*(d[i][j]-u[i][j]+1)==con[i][j]) can.insert(make_pair(make_pair(l[i][j],r[i][j]),make_pair(u[i][j],d[i][j])));
            }
        }
        return (long long) can.size();
    }
    return ans;

}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'void F(int, int, int, int)':
rect.cpp:35:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |     if(y+1!=M&&(tt[x][y]>tt[x][y+1]||tt[x][y]==tt[x][y+1]&&!have[x][y+1]))
rect.cpp:44:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   44 |     if(y-1!=0&&(tt[x][y]>tt[x][y-1]||tt[x][y]==tt[x][y-1]&&!have[x][y-1]))
rect.cpp:53:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   53 |     if(x+1!=N&&(tt[x][y]>tt[x+1][y]||tt[x][y]==tt[x+1][y]&&!have[x+1][y]))
rect.cpp:62:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |     if(x-1!=0&&(tt[x][y]>tt[x-1][y]||tt[x][y]==tt[x-1][y]&&!have[x-1][y]))
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:78:18: warning: unused variable 'm' [-Wunused-variable]
   78 |     int i,j,k,ll,m,n,big=0,ok,now=0;
      |                  ^
rect.cpp:78:20: warning: unused variable 'n' [-Wunused-variable]
   78 |     int i,j,k,ll,m,n,big=0,ok,now=0;
      |                    ^

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