Submission #875877

#	Time	Username	Problem	Language	Result	Execution time	Memory
875877		andrei_boaca	Rectangles (IOI19_rect)	C++17	72 / 100	5073 ms	171760 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
int v[2505][2505],n,m,up[2505][2505],down[2505][2505],rmq[15][2505],loga[2505],dlin[2505],ulin[2505],lins[2505],valmax[2505];
vector<int> who[2505];
int good[2505],last[2505];
int plin[2505][2505],pcol[2505][2505],s[2505][2505];
int aib[2505];
int getmax(int l,int r)
{
    int lg=loga[r-l+1];
    return max(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}
int suma(int poz)
{
    int rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
int getsum(int is,int js,int ij,int jj)
{
    return s[ij][jj]-s[is-1][jj]-s[ij][js-1]+s[is-1][js-1];
}
long long zerounu()
{
    ll ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+v[i][j];
    for(int i=2;i<n;i++)
    {
        pcol[i][m]=0;
        for(int j=m-1;j>=2;j--)
        {
            if(v[i][j]==1)
            {
                pcol[i][j]=0;
                continue;
            }
            if(v[i][j+1]==1)
                pcol[i][j]=j;
            else
                pcol[i][j]=pcol[i][j+1];
        }
    }
    for(int j=2;j<m;j++)
    {
        plin[n][j]=0;
        for(int i=n-1;i>=2;i--)
        {
            if(v[i][j]==1)
            {
                plin[i][j]=0;
                continue;
            }
            if(v[i+1][j]==1)
                plin[i][j]=i;
            else
                plin[i][j]=plin[i+1][j];
        }
    }
    for(int i=2;i<n;i++)
        for(int j=2;j<m;j++)
            if(plin[i][j]>=i&&pcol[i][j]>=j)
            {
                int l1=i,c1=j,l2=plin[i][j],c2=pcol[i][j];
                if(getsum(l1,c1,l2,c2)==0)
                    if(getsum(l1,c1-1,l2,c1-1)==l2-l1+1&&getsum(l1,c2+1,l2,c2+1)==l2-l1+1)
                        if(getsum(l1-1,c1,l1-1,c2)==c2-c1+1&&getsum(l2+1,c1,l2+1,c2)==c2-c1+1)
                            ans++;
            }
    return ans;
}
long long count_rectangles(vector<vector<int>> A)
{
    ll ans=0;
    n=A.size();
    m=A[0].size();
    for(int i=1;i<=2500;i++)
    {
        for(int bit=0;bit<=13;bit++)
            if((1<<bit)<=i)
                loga[i]=bit;
    }
    if(n<=2||m<=2)
        return 0;
    bool sub6=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            v[i][j]=A[i-1][j-1];
            if(v[i][j]>1)
                sub6=0;
        }
    if(sub6)
        return zerounu();
    for(int j=1;j<=m;j++)
    {
        for(int i=n;i>=1;i--)
        {
            rmq[0][i]=v[i][j];
            for(int k=1;k<=13;k++)
            {
                rmq[k][i]=rmq[k-1][i];
                int poz=i+(1<<(k-1));
                if(poz<=n)
                    rmq[k][i]=max(rmq[k][i],rmq[k-1][poz]);
            }
        }
        for(int i=2;i<n;i++)
        {
            up[i][j]=1e9;
            down[i][j]=0;
            int st=i;
            int dr=n-1;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(getmax(i,mij)<v[i-1][j])
                {
                    down[i][j]=mij;
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            st=2;
            dr=i;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(getmax(mij,i)<v[i+1][j])
                {
                    up[i][j]=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
        }
    }
    for(int c1=2;c1<m;c1++)
    {
        for(int i=2;i<n;i++)
        {
            dlin[i]=1e9;
            ulin[i]=0;
            valmax[i]=-1;
        }
        for(int c2=c1;c2<m;c2++)
        {
            for(int i=2;i<n;i++)
                who[i].clear();
            for(int i=2;i<n;i++)
            {
                valmax[i]=max(valmax[i],v[i][c2]);
                dlin[i]=min(dlin[i],down[i][c2]);
                ulin[i]=max(ulin[i],up[i][c2]);
                if(valmax[i]<v[i][c1-1]&&valmax[i]<v[i][c2+1])
                    good[i]=1;
                else
                    good[i]=0;
                if(ulin[i]>=2&&ulin[i]<n&&good[i])
                    who[ulin[i]].push_back(i);
            }
            for(int i=n-1;i>=2;i--)
            {
                if(!good[i])
                {
                    last[i]=0;
                    continue;
                }
                if(good[i+1])
                    last[i]=last[i+1];
                else
                    last[i]=i;
            }
            for(int i=1;i<=n;i++)
                aib[i]=0;
            for(int i=2;i<n;i++)
            {
                for(int j:who[i])
                    update(j,1);
                if(good[i])
                {
                    int st=i;
                    int dr=min(dlin[i],last[i]);
                    if(st<=dr)
                    {
                        int val=suma(dr)-suma(st-1);
                        ans+=val;
                    }
                }
            }
        }
    }
    return ans;
}

• 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: 0 / 28