Submission #762309

#	Time	Username	Problem	Language	Result	Execution time	Memory
762309		alexander707070	Rectangles (IOI19_rect)	C++14	0 / 100	84 ms	89604 KiB

rect

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

int a[MAXN][MAXN],ans,cnt[MAXN][MAXN],last[MAXN][MAXN];
bool eq[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]){
                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(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 ok(int x,int y,int l){
    for(int i:lens[x][y]){
        if(i==l)return true;
    }
    return false;
}

bool okrow(int w,int l,int r){
    int maxs=0;
    for(int i=l;i<=r;i++){
        maxs=max(maxs,a[w][i]);
    }
    return maxs<a[w][l-1] and maxs<a[w][r+1];
}
 
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();

    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;

            br=0;
            for(int p=i;p>=1;p--){
                if(okrow(p,l,r))br++;
                else break;
            }

            for(int k:lens[i][r]){
                if(k>br)continue;

                for(int p=l;p<=r;p++){
                    if(!ok(i,p,k))break;
                    else if(p==r)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;
}
*/

• 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