Submission #298836

#	Time	Username	Problem	Language	Result	Execution time	Memory
298836		daniel920712	Rectangles (IOI19_rect)	C++14	0 / 100	2 ms	1664 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)
{
    //printf("%d %d %d %d\n",x,y,sx,sy);
    if(have[x][y]) return ;
    if(tt[x][y]==tt[sx][sy]) sa.push_back(make_pair(sx,sy));
    //printf("bb %d %d\n",x,y);
    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!=-1&&(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!=-1&&(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,now=0;
    tt=all;
    N=all.size();
    M=all[0].size();
    for(i=0;i<N;i++)
    {
        for(j=0;j<M;j++)
        {
            how[now].x=i;
            how[now].y=j;
            how[now].con=all[i][j];
            now++;
        }
    }
    sort(how,how+N*M,cmp);
    for(i=0;i<N*M;i++)
    {
        //printf("%d %d %d\n",i,how[i].x,how[i].y);
        if(!have[how[i].x][how[i].y])
        {
            //printf("aa\n");
            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++)
        {
            //printf("%d %d %d %d %d %d %d\n",i,j,l[i][j],r[i][j],u[i][j],d[i][j],con[i][j]);
            if((r[i][j]-l[i][j]+1)*(d[i][j]-u[i][j]+1)==con[i][j]&&l[i][j]!=0&&r[i][j]!=M-1&&u[i][j]!=0&&d[i][j]!=N-1) 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();


}

Compilation message (stderr)

rect.cpp: In function 'void F(int, int, int, int)':
rect.cpp:37:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   37 |     if(y+1!=M&&(tt[x][y]>tt[x][y+1]||tt[x][y]==tt[x][y+1]&&!have[x][y+1]))
rect.cpp:46:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   46 |     if(y-1!=-1&&(tt[x][y]>tt[x][y-1]||tt[x][y]==tt[x][y-1]&&!have[x][y-1]))
rect.cpp:55:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   55 |     if(x+1!=N&&(tt[x][y]>tt[x+1][y]||tt[x][y]==tt[x+1][y]&&!have[x+1][y]))
rect.cpp:64:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   64 |     if(x-1!=-1&&(tt[x][y]>tt[x-1][y]||tt[x][y]==tt[x-1][y]&&!have[x-1][y]))

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