Submission #867088

#	Time	Username	Problem	Language	Result	Execution time	Memory
867088		abcvuitunggio	Rectangles (IOI19_rect)	C++17	Compilation error	0 ms	0 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
int n,m,l[2501][2501],r[2501][2501],u[2501][2501],d[2501][2501],cnt,nxt[2501][2501][4];
stack <pair <int, int>> st;
vector <pair <pair <int, int>, pair <int, int>>> ve;
long long count_rectangles(vector <vector <int>> a){
    n=a.size(),m=a[0].size();
    for (int i=0;i<n;i++){
        while (!st.empty())
            st.pop();
        for (int j=0;j<m;j++){
            while (!st.empty()&&st.top().first<a[i][j])
                st.pop();
            l[i][j]=(st.empty()?-1:st.top().second);
            st.push({a[i][j],j});
        }
        while (!st.empty())
            st.pop();
        for (int j=m-1;j>=0;j--){
            while (!st.empty()&&st.top().first<a[i][j])
                st.pop();
            r[i][j]=(st.empty()||st.top().first==a[i][j]?-1:st.top().second);
            st.push({a[i][j],j});
        }
    }
    for (int j=0;j<m;j++){
        while (!st.empty())
            st.pop();
        for (int i=0;i<n;i++){
            while (!st.empty()&&st.top().first<a[i][j])
                st.pop();
            u[i][j]=(st.empty()?-1:st.top().second);
            st.push({a[i][j],i});
        }
        while (!st.empty())
            st.pop();
        for (int i=n-1;i>=0;i--){
            while (!st.empty()&&st.top().first<a[i][j])
                st.pop();
            d[i][j]=(st.empty()||st.top().first==a[i][j]?-1:st.top().second);
            st.push({a[i][j],i});
        }
    }
    for (int i=1;i<n-1;i++)
        for (int j=1;j<m-1;j++){
            int r1,c1,r2,c2;
            r1=u[i+1][j];
            c1=j-1;
            r2=i+1;
            if (r1!=-1)
                c2=r[r1+1][c1];
            if (r1!=-1&&c2!=-1)
                ve.push_back({{r1,r2},{c1,c2}});
            c2=j+1;
            if (r1!=-1)
                c1=l[r1+1][c2];
            if (r1!=-1&&c1!=-1)
                ve.push_back({{r1,r2},{c1,c2}});
            r1=i-1;
            c1=j-1;
            r2=d[r1][c1+1];
            c2=r[r1+1][c1];
            if (r2!=-1&&c2!=-1)
                ve.push_back({{r1,r2},{c1,c2}});
            c2=j+1;
            r2=d[r1][c2-1];
            c1=l[r1+1][c2];
            if (r2!=-1&&c1!=-1)
                ve.push_back({{r1,r2},{c1,c2}});
        }
    memset(nxt,-1,sizeof(nxt));
    for (int i=n-1;i>=0;i--)
        for (int j=m-1;j>=0;j--){
            int k=l[i][j];
            if (k!=-1){
                nxt[i][j][0]=i;
                if (i<n-1){
                    if (r[i+1][k]==j)
                        nxt[i][j][0]=nxt[i+1][k][1];
                    else if (l[i+1][j]==k)
                        nxt[i][j][0]=nxt[i+1][j][0];
                }
            }
            k=r[i][j];
            if (k!=-1){
                nxt[i][j][1]=i;
                if (i<n-1){
                    if (l[i+1][k]==j)
                        nxt[i][j][1]=nxt[i+1][k][0];
                    else if (r[i+1][j]==k)
                        nxt[i][j][1]=nxt[i+1][j][1];
                }
            }
        }
    for (int j=m-1;j>=0;j--)
        for (int i=n-1;i>=0;i--){
            int k=u[i][j];
            if (k!=-1){
                nxt[i][j][2]=j;
                if (j<m-1){
                    if (d[k][j+1]==i)
                        nxt[i][j][2]=nxt[k][j+1][3];
                    else if (u[i][j+1]==k)
                        nxt[i][j][2]=nxt[i][j+1][2];
                }
            }
            k=d[i][j];
            if (k!=-1){
                nxt[i][j][3]=j;
                if (j<m-1){
                    if (u[k][j+1]==i)
                        nxt[i][j][3]=nxt[k][j+1][2];
                    else if (d[i][j+1]==k)
                        nxt[i][j][3]=nxt[i][j+1][3];
                }
            }
        }
    for (auto [p,q]:ve){
        auto [r1,r2]=p;
        auto [c1,c2]=q;
        if (r2-r1>1&&c2-c1>1&&((u[r2][c1+1]==r1&&nxt[r2][c1+1][2]>=c2-1)||(d[r1][c1+1]==r2&&nxt[r1][c1+1][3]>=c2-1))&&((l[r1+1][c2]==c1&&nxt[r1+1][c2][0]>=r2-1)||(r[r1+1][c1]==c2&&nxt[r1+1][c1][1]>=r2-1))){
            cnt++;
            mp[{p,q}]=0;
        }
    }
	return cnt;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:124:13: error: 'mp' was not declared in this scope; did you mean 'p'?
  124 |             mp[{p,q}]=0;
      |             ^~
      |             p