Submission #875905

#	Time	Username	Problem	Language	Result	Execution time	Memory
875905		andrei_boaca	Rectangles (IOI19_rect)	C++17	100 / 100	2181 ms	423036 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],rdown[15][2505],rup[15][2505],loga[2505],dlin[2505],ulin[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];
ll ans;
struct date
{
    int poz,up,down;
};
vector<date> lins[2505][2505];
int lft[2505],rgt[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 getup(int l,int r)
{
    int lg=loga[r-l+1];
    return max(rup[lg][l],rup[lg][r-(1<<lg)+1]);
}
int getdown(int l,int r)
{
    int lg=loga[r-l+1];
    return min(rdown[lg][l],rdown[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;
}
bool comp(date a, date b)
{
    return a.up<b.up;
}
bool bypoz(date a, date b)
{
    return a.poz<b.poz;
}
void calc(vector<date> a)
{
    vector<date> aux=a;
    sort(aux.begin(),aux.end(),comp);
    reverse(aux.begin(),aux.end());
    sort(a.begin(),a.end(),bypoz);
    vector<int> toerase;
    for(int i=0;i<a.size();i++)
    {
        while(!aux.empty()&&aux.back().up<=a[i].poz)
        {
            update(aux.back().poz,1);
            toerase.push_back(aux.back().poz);
            aux.pop_back();
        }
        int l=a[i].poz;
        int r=min(a[i].down,a.back().poz);
        if(l<=r)
            ans+=suma(r)-suma(l-1);
    }
    for(int i:toerase)
        update(i,-1);
}
long long count_rectangles(vector<vector<int>> A)
{
    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;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            v[i][j]=A[i-1][j-1];
    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 i=2;i<n;i++)
    {
        for(int j=m;j>=1;j--)
        {
            lft[j]=0;
            rgt[j]=m+1;
            rup[0][j]=up[i][j];
            rdown[0][j]=down[i][j];
            for(int k=1;k<=13;k++)
            {
                rup[k][j]=rup[k-1][j];
                rdown[k][j]=rdown[k-1][j];
                int poz=j+(1<<(k-1));
                if(poz<=m)
                {
                    rup[k][j]=max(rup[k][j],rup[k-1][poz]);
                    rdown[k][j]=min(rdown[k][j],rdown[k-1][poz]);
                }
            }
        }
        deque<int> coada;
        for(int j=1;j<=m;j++)
        {
            while(!coada.empty()&&v[i][j]>=v[i][coada.back()])
                coada.pop_back();
            if(coada.empty())
                lft[j]=0;
            else
                lft[j]=coada.back()+1;
            coada.push_back(j);
        }
        coada.clear();
        for(int j=m;j>=1;j--)
        {
            while(!coada.empty()&&v[i][j]>=v[i][coada.back()])
                coada.pop_back();
            if(coada.empty())
                rgt[j]=m+1;
            else
                rgt[j]=coada.back()-1;
            coada.push_back(j);
        }
        for(int j=1;j<=m;j++)
        {
            int l=lft[j],r=rgt[j];
            if(l>=2&&r<=m-1&&l<=r)
                lins[l][r].push_back({i,getup(l,r),getdown(l,r)});
        }
    }
    for(int c1=2;c1<m;c1++)
        for(int c2=c1;c2<m;c2++)
            if(lins[c1][c2].size()>=1)
            {
                vector<date> a=lins[c1][c2];
                sort(a.begin(),a.end(),bypoz);
                vector<date> vals;
                for(int i=0;i<a.size();i++)
                {
                    if(i>0&&a[i].poz==a[i-1].poz)
                        continue;
                    if(i==0||a[i].poz==a[i-1].poz+1)
                        vals.push_back(a[i]);
                    else
                    {
                        calc(vals);
                        vals.clear();
                        vals.push_back(a[i]);
                    }
                }
                if(!vals.empty())
                    calc(vals);
            }
    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'void calc(std::vector<date>)':
rect.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<date>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<a.size();i++)
      |                 ~^~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:196:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<date>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |                 for(int i=0;i<a.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