Submission #410015

#	Time	Username	Problem	Language	Result	Execution time	Memory
410015		rumen_m	Rectangles (IOI19_rect)	C++17	0 / 100	61 ms	98732 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2505;
struct segment
{
    int segm[maxn];
    segment ()
    {
        int i;
        for(i=0;i<maxn;i++)
            segm[i] = 1e9;
    }
    void update(int v, int l, int r, int x, int delta)
    {
        if(l==r)
        {
            if(delta!=0)
            segm[v] = delta;
            return ;
        }
        int mid = (l+r)/2;
        if(x<=mid)update(2*v,l,mid,x,delta);
        else
            update(2*v+1,mid+1,r,x,delta);
        segm[v] = min(segm[2*v],segm[2*v+1]);
    }
    int query(int v, int from, int to, int l, int r)
    {
        if(l<=from&&to<=r)return segm[v];
        int mid = (from+to)/2;
        int ans = 1e9;
        if(l<=mid)ans = query(2*v,from,mid,l,r);
        if(r>mid)ans = min(ans,query(2*v+1,mid+1,to,l,r));
        return ans;
    }
};
segment l[maxn],r[maxn],d[maxn],u[maxn];
vector<vector<int> > a;
stack <int> k,empt;
struct rect
{
    int x1,x2,y1,y2;
};
rect b[maxn][maxn];
vector <rect> f;
rect S;
int p[maxn];
bool cmp(rect i, rect j)
{
    if(i.x1==j.x1)
    {
        if(i.y1==j.y1)
        {
            if(i.x2==j.x2)
                return i.y2<j.y2;
            return i.x2<j.x2;
        }
        return i.y1<j.y1;
    }
    return i.x1<j.x1;
}
int ANS = 0;
int n,m;
bool check(rect a)
{
    //cout<<"CHECK: "<<a.x1<<" "<<a.y1<<" : "<<a.x2<<" "<<a.y2<<" || "<<r[a.x1-1].query(1,0,m,a.x1,a.x2)<<" "<<l[a.x2+1].query(1,0,m,a.x1,a.x2)<<" "<<u[a.y1-1].query(1,0,n,a.y1,a.y2)<<" "<<d[a.y2+1].query(1,0,n,a.y1,a.y2)<<endl;
    if(r[a.x1-1].query(1,0,m,a.x1,a.x2)<=a.y2-a.y1+1)return false;
    if(l[a.x2+1].query(1,0,m,a.x1,a.x2)<=a.y2-a.y1+1)return false;
    if(u[a.y1-1].query(1,0,n,a.y1,a.y2)<=a.x2-a.x1+1)return false;
    if(d[a.y2+1].query(1,0,n,a.y1,a.y2)<=a.x2-a.x1+1)return false;
   // cout<<"YES"<<endl;
    return true;
}
long long count_rectangles(std::vector<std::vector<int> > _a) {
	a = _a;
	int i,j;
	 n = a.size();
	 m = a[0].size();
	for(i=0;i<=n-1;i++)
    {
        k = empt;

       // k.push(0);
        for(j=0;j<=m-1;j++)
        {
            while(!k.empty()&&a[i][j]>=a[i][k.top()])k.pop();
           if(!k.empty()) b[i][j].x1 = j-k.top();
           else
                b[i][j].x1 = 0;
            l[j].update(1,0,m,i,b[i][j].x1);
            k.push(j);
        }

    }

    for(i=0;i<=n-1;i++)
    {
        k = empt;

        //k.push(m-1);
        for(j=m-1;j>=0;j--)
        {
            while(!k.empty()&&a[i][j]>=a[i][k.top()])k.pop();
           if(!k.empty()) b[i][j].x2 = k.top()-j;
           else
                b[i][j].x2 = 0;
            r[j].update(1,0,m,i,b[i][j].x2);
             k.push(j);
        }

    }
    for(i=0;i<=m-1;i++)
    {
        k = empt;

        //k.push(0);
        for(j=0;j<=n-1;j++)
        {
            while(!k.empty()&&a[j][i]>=a[k.top()][i])k.pop();
           if(!k.empty()) b[j][i].y1 = j-k.top();
           else
                b[j][i].y1 = 0;
            u[j].update(1,0,n,i,b[j][i].y1);
             k.push(j);
        }

    }
    for(i=0;i<=m-1;i++)
    {
        k = empt;

        //k.push(n-1);
        for(j=n-1;j>=0;j--)
        {
            while(!k.empty()&&a[j][i]>=a[k.top()][i])k.pop();
           if(!k.empty()) b[j][i].y2 = k.top()-j;
           else
                b[j][i].y2 = 0;
            d[j].update(1,0,n,i,b[j][i].y2);
             k.push(j);
        }

    }
    ////////////////////////////
    for(i=0;i<=n-1;i++)
    {
        k = empt;

       // k.push(0);
        for(j=0;j<=m-1;j++)
        {
            while(!k.empty()&&a[i][j]>a[i][k.top()])k.pop();
           if(!k.empty()) b[i][j].x1 = j-k.top();
           else
                b[i][j].x1 = 0;
           // l[j].update(1,0,n,i,b[i][j].x1);
            k.push(j);
        }

    }

    for(i=0;i<=n-1;i++)
    {
        k = empt;

        //k.push(m-1);
        for(j=m-1;j>=0;j--)
        {
            while(!k.empty()&&a[i][j]>a[i][k.top()])k.pop();
           if(!k.empty()) b[i][j].x2 = k.top()-j;
           else
                b[i][j].x2 = 0;
           // r[j].update(1,0,n,i,b[i][j].x2);
             k.push(j);
        }

    }
    for(i=0;i<=m-1;i++)
    {
        k = empt;

        //k.push(0);
        for(j=0;j<=n-1;j++)
        {
            while(!k.empty()&&a[j][i]>a[k.top()][i])k.pop();
           if(!k.empty()) b[j][i].y1 = j-k.top();
           else
                b[j][i].y1 = 0;
          //  u[j].update(1,0,m,i,b[j][i].y1);
             k.push(j);
        }

    }
    for(i=0;i<=m-1;i++)
    {
        k = empt;

        //k.push(n-1);
        for(j=n-1;j>=0;j--)
        {
            while(!k.empty()&&a[j][i]>a[k.top()][i])k.pop();
           if(!k.empty()) b[j][i].y2 = k.top()-j;
           else
                b[j][i].y2 = 0;
          //  d[j].update(1,0,m,i,b[j][i].y2);
             k.push(j);
        }

    }
    for(i=1;i<=n-2;i++)
        for(j=1;j<=m-2;j++)
    {
      //  cout<<i<<" "<<j<<"-> "<<b[i][j].x1<<" "<<b[i][j].x2<<" "<<b[i][j].y1<<" "<<b[i][j].y2<<endl;
        if(b[i][j].x1==0||b[i][j].x2==0||b[i][j].y1==0||b[i][j].y2==0)continue;
        S.x1 = j - b[i][j].x1+1;
        S.x2 = j + b[i][j].x2-1;
        S.y1 = i - b[i][j].y1+1;
        S.y2 = i + b[i][j].y2-1;
        f.push_back(S);
    }
    sort(f.begin(),f.end(),cmp);
    for(i=0;i<f.size();i++)
    {
        if(i>0)
        {
            if(f[i-1].x1==f[i].x1&&f[i-1].x2==f[i].x2&&f[i-1].y1==f[i].y1&&f[i-1].y2==f[i].y2)
                continue;
        }
      ANS+=  check(f[i]);
    }
    return ANS;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 8 7 5 6
*/

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:223:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |     for(i=0;i<f.size();i++)
      |             ~^~~~~~~~~

• 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