Submission #762422

#	Time	Username	Problem	Language	Result	Execution time	Memory
762422		alexander707070	Rectangles (IOI19_rect)	C++14	100 / 100	4283 ms	753624 KiB

rect

#include<bits/stdc++.h>
#define MAXN 2507
using namespace std;
 
int n,m,prow[MAXN][MAXN],nrow[MAXN][MAXN],l,r;
int pcol[MAXN][MAXN],ncol[MAXN][MAXN];
stack<int> st;
vector<int> lens[MAXN][MAXN],pre[MAXN][MAXN];

int a[MAXN][MAXN],ans,cnt[MAXN][MAXN],last[MAXN][MAXN];
int ocurr[MAXN],br[MAXN];
bool eq[MAXN][MAXN],qe[MAXN][MAXN];

void calc_intervals(){
    for(int i=1;i<=n;i++){
        while(!st.empty())st.pop();
        for(int f=1;f<=m;f++){
            while(!st.empty() and a[i][f]>=a[i][st.top()]){
                if(a[i][f]==a[i][st.top()])eq[i][f]=true;
                st.pop();
            }
            if(!st.empty())prow[i][f]=st.top();
            st.push(f);
        }

        while(!st.empty())st.pop();
        for(int f=m;f>=1;f--){
            while(!st.empty() and a[i][f]>=a[i][st.top()]){
                st.pop();
            }
            if(!st.empty())nrow[i][f]=st.top();
            st.push(f);
        }
    }

    for(int f=1;f<=m;f++){
        while(!st.empty())st.pop();
        for(int i=1;i<=n;i++){
            while(!st.empty() and a[i][f]>=a[st.top()][f]){
                if(a[i][f]==a[st.top()][f])qe[i][f]=true;
                st.pop();
            }
            if(!st.empty())pcol[i][f]=st.top();
            st.push(i);
        }

        while(!st.empty())st.pop();
        for(int i=n;i>=1;i--){
            while(!st.empty() and a[i][f]>=a[st.top()][f]){
                st.pop();
            }
            if(!st.empty())ncol[i][f]=st.top();
            st.push(i);
        }

        for(int i=1;i<=n;i++){
            if(!qe[i][f] and ncol[i][f]<=n and pcol[i][f]>=1){
                lens[ncol[i][f]-1][f].push_back(ncol[i][f]-pcol[i][f]-1);
            }
        }
    }
}

bool dali;

void calc_previous(){
    for(int i=1;i<=n;i++){
        for(int f=1;f<=n;f++){
            br[f]=0; ocurr[f]=0;
        }

        for(int f=1;f<=m;f++){
            pre[i][f].resize(int(lens[i][f].size()));

            for(int k=0;k<lens[i][f].size();k++){
                if(ocurr[lens[i][f][k]]==f-1)br[lens[i][f][k]]++;
                else br[lens[i][f][k]]=1;

                ocurr[lens[i][f][k]]=f;

                pre[i][f][k]=f-br[lens[i][f][k]];
            }
        }
    }
}

long long count_rectangles(vector< vector<int> > A){
    n=int(A.size()); m=int(A[0].size());
 
    for(int i=1;i<=n;i++){
        for(int f=1;f<=m;f++){
            a[i][f]=A[i-1][f-1];
            pcol[i][f]=prow[i][f]=0;
            ncol[i][f]=nrow[i][f]=max(n,m)+1;
        }
    }

    calc_intervals();
    calc_previous();

    for(int i=2;i<=m-1;i++){
        for(int f=i;f<=m-1;f++){
            last[i][f]=1;
        }
    }

    for(int i=2;i<=n-1;i++){

        for(int f=2;f<=m-1;f++){
            l=prow[i][f]+1; r=nrow[i][f]-1;
            if(l<2 or r>m-1 or eq[i][f])continue;

            if(last[l][r]==i-1)cnt[l][r]++;
            else cnt[l][r]=1;
            
            last[l][r]=i;
        }

        for(int f=2;f<=m-1;f++){
            l=prow[i][f]+1; r=nrow[i][f]-1;
            if(l<2 or r>m-1 or eq[i][f])continue;

            for(int k=0;k<lens[i][r].size();k++){
                if(lens[i][r][k]>cnt[l][r])continue;
                if(pre[i][r][k]<l)ans++;
            }
        }
    }
    
    return ans;
}
 
/*
int main(){
 
    cout<<count_rectangles({{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, 5, 13, 5, 6}})<<"\n";
 
    return 0;
}
*/

Compilation message (stderr)

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

• 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