Submission #571437

#	Time	Username	Problem	Language	Result	Execution time	Memory
571437		azberjibiou	Rectangles (IOI19_rect)	C++17	100 / 100	4368 ms	578432 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
const int mxN=2505;
typedef struct rect{
    short x1, x2, y1, y2;
    rect() : x1(0), x2(0), y1(0), y2(0) {}
    rect(short x1, short x2, short y1, short y2) : x1(x1), x2(x2), y1(y1), y2(y2) {}
    bool operator==(rect a)
    {
        return (a.x1==x1 && a.x2==x2 && a.y1==y1 && a.y2==y2);
    }
}rect;
typedef struct qry{
    short s, e, rowcol;
    int idx;
    qry() : s(0), e(0), rowcol(0), idx(0) {}
    qry(short s, short e, short rowcol, int idx) : s(s), e(e), rowcol(rowcol), idx(idx) {}
}qry;
short N, M;
int A[mxN][mxN];
short L[mxN][mxN], R[mxN][mxN], U[mxN][mxN], D[mxN][mxN];
vector <rect> v;
bool Chk[mxN*mxN];
vector <qry> cont[4][mxN];
bool cmp1(rect a, rect b)
{
    if(a.x1!=b.x1)  return a.x1<b.x1;
    if(a.x2!=b.x2)  return a.x2<b.x2;
    if(a.y1!=b.y1)  return a.y1<b.y1;
    return a.y2<b.y2;
}
void make_LRUD1()
{
    for(short i=1;i<N-1;i++)
    {
        stack <short> stk;
        for(short j=0;j<M;j++)
        {
            while(!stk.empty() && A[i][stk.top()]<=A[i][j])   stk.pop();
            L[i][j]=(stk.empty() ? -1 : stk.top());
            stk.push(j);
        }
        while(!stk.empty()) stk.pop();
        for(short j=M-1;j>=0;j--)
        {
            while(!stk.empty() && A[i][stk.top()]<=A[i][j])   stk.pop();
            R[i][j]=(stk.empty() ? M : stk.top());
            stk.push(j);
        }
    }
    for(short i=1;i<M-1;i++)
    {
        stack <short> stk;
        for(short j=0;j<N;j++)
        {
            while(!stk.empty() && A[stk.top()][i]<=A[j][i]) stk.pop();
            U[j][i]=(stk.empty() ? -1 : stk.top());
            stk.push(j);
        }
        while(!stk.empty()) stk.pop();
        for(short j=N-1;j>=0;j--)
        {
            while(!stk.empty() && A[stk.top()][i]<=A[j][i]) stk.pop();
            D[j][i]=(stk.empty() ? N : stk.top());
            stk.push(j);
        }
    }
}
void make_LRUD2()
{
    for(short i=1;i<N-1;i++)
    {
        stack <short> stk;
        for(short j=0;j<M;j++)
        {
            while(!stk.empty() && A[i][stk.top()]<A[i][j])   stk.pop();
            L[i][j]=(stk.empty() ? -1 : stk.top());
            stk.push(j);
        }
        while(!stk.empty()) stk.pop();
        for(short j=M-1;j>=0;j--)
        {
            while(!stk.empty() && A[i][stk.top()]<A[i][j])   stk.pop();
            R[i][j]=(stk.empty() ? M : stk.top());
            stk.push(j);
        }
    }
    for(short i=1;i<M-1;i++)
    {
        stack <short> stk;
        for(short j=0;j<N;j++)
        {
            while(!stk.empty() && A[stk.top()][i]<A[j][i]) stk.pop();
            U[j][i]=(stk.empty() ? -1 : stk.top());
            stk.push(j);
        }
        while(!stk.empty()) stk.pop();
        for(short j=N-1;j>=0;j--)
        {
            while(!stk.empty() && A[stk.top()][i]<A[j][i]) stk.pop();
            D[j][i]=(stk.empty() ? N : stk.top());
            stk.push(j);
        }
    }
}
short seg[4*mxN];
void init(short idx, short s, short e, short lrud, short rowcol)  ///DURL
{
    if(s==e)
    {
        if(lrud==0) seg[idx]=D[rowcol][s];
        if(lrud==1) seg[idx]=U[rowcol][s];
        if(lrud==2) seg[idx]=R[s][rowcol];
        if(lrud==3) seg[idx]=L[s][rowcol];
        return;
    }
    short mid=(s+e)/2;
    init(2*idx, s, mid, lrud, rowcol);
    init(2*idx+1, mid+1, e, lrud, rowcol);
    if(lrud==0 || lrud==2)  seg[idx]=min(seg[2*idx], seg[2*idx+1]);
    else    seg[idx]=max(seg[2*idx], seg[2*idx+1]);
}
short lim;
bool typ;
bool solvl(short idx, short s1, short e1, short s2)
{
    if(s2==s1)  return (typ ? seg[idx]<=lim : seg[idx]>=lim);
    while(s2<=e1)
    {
        short mid=(s1+e1)/2;
        if(s2<=mid+1)
        {
            if(typ ? seg[2*idx+1]>lim : seg[2*idx+1]<lim)   return false;
            idx*=2; e1=mid;
        }
        else    idx=2*idx+1, s1=mid+1;
    }
    return true;
}
bool solvr(short idx, short s1, short e1, short e2)
{
    if(e2==e1)  return (typ ? seg[idx]<=lim : seg[idx]>=lim);
    while(e2>=s1)
    {
        short mid=(s1+e1)/2;
        if(e2>=mid)
        {
            if(typ ? seg[2*idx]>lim : seg[2*idx]<lim)   return false;
            idx=2*idx+1, s1=mid+1;
        }
        else    idx*=2, e1=mid;
    }
    return true;
}
bool solv(short s1, short e1, short s2, short e2)
{
    short idx=1;
    while(s1!=e1)
    {
        short mid=(s1+e1)/2;
        if(e2<=mid) e1=mid, idx*=2;
        else if(s2>mid) s1=mid+1, idx=2*idx+1;
        else    break;
    }
    if(s1==e1)  return (typ ? seg[idx]<=lim : seg[idx]>=lim);
    short mid=(s1+e1)/2;
    return (solvl(2*idx, s1, mid, s2) && solvr(2*idx+1, mid+1, e1, e2));
}
void make_seg()
{
    for(short i=0;i<N;i++)
    {
        init(1, 0, M-1, 0, i);  typ=false;
        for(auto ele : cont[0][i])
        {
            lim=ele.rowcol;
            if(!solv(0, M-1, ele.s, ele.e))    Chk[ele.idx]=false;
        }
        init(1, 0, M-1, 1, i);  typ=true;
        for(auto ele : cont[1][i])
        {
            lim=ele.rowcol;
            if(!solv(0, M-1, ele.s, ele.e))    Chk[ele.idx]=false;
        }
    }
    for(short i=0;i<M;i++)
    {
        init(1, 0, N-1, 2, i);  typ=false;
        for(auto ele : cont[2][i])
        {
            lim=ele.rowcol;
            if(!solv(0, N-1, ele.s, ele.e))    Chk[ele.idx]=false;
        }
        init(1, 0, N-1, 3, i);  typ=true;
        for(auto ele : cont[3][i])
        {
            lim=ele.rowcol;
            if(!solv(0, N-1, ele.s, ele.e))    Chk[ele.idx]=false;
        }
    }
}
long long count_rectangles(std::vector<std::vector<int> > a) {
    N=a.size();
    M=a[0].size();
    for(short i=0;i<N;i++)    for(short j=0;j<M;j++)    A[i][j]=a[i][j];
    make_LRUD1();
    for(short i=1;i<N-1;i++)
    {
        for(short j=1;j<M-1;j++)
        {
            if(U[i][j]!=-1 && D[i][j]!=N && L[i][j]!=-1 && R[i][j]!=M)  v.emplace_back(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1);
        }
    }
    sort(v.begin(), v.end(), cmp1);
    v.erase(unique(v.begin(), v.end()), v.end());
    make_LRUD2();
    for(int i=0;i<v.size();i++)
    {
        rect ele=v[i];
        Chk[i]=true;
        cont[0][ele.x1-1].emplace_back(ele.y1, ele.y2, ele.x2+1, i);
        cont[1][ele.x2+1].emplace_back(ele.y1, ele.y2, ele.x1-1, i);
        cont[2][ele.y1-1].emplace_back(ele.x1, ele.x2, ele.y2+1, i);
        cont[3][ele.y2+1].emplace_back(ele.x1, ele.x2, ele.y1-1, i);
    }
    make_seg();
    int ans=0;
    for(int i=0;i<v.size();i++) ans+=Chk[i];
    return ans;
}

Compilation message (stderr)

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