If \(A\) does not contain \(0\)

First of all, for simplicity, we consider the case where \(A\) does not contain \(0\).

\(A\) satisfies the condition in the Problem Statement,

\[A_{1, 1} \leq A_{1, 2} \leq \cdots \leq A_{1, W} \leq A_{2, 1} \leq A_{2, 2} \leq \cdots \leq A_{2, W} \leq A_{3, 1} \leq \cdots \leq A_{H-1, W} \leq A_{H, 1} \leq A_{H, 2} \leq \cdots \leq A_{H, W},\]

if and only if \(A\) satisfies both of the following two conditions:

1. \(m_1 \leq M_1 \leq m_2 \leq M_2 \leq m_3 \leq \cdots \leq m_H \leq M_H\), where \(m_i\) denotes the minimum value of the \(i\)-th row and \(M_i\) the maximum; and

2. for all \(j = 1, 2, \ldots, W-1\), the following holds:

   • for all row \(i\), \(A_{i, j} \leq A_{i, j+1}\).

The operation of swapping rows and swapping columns are commutable. In addition, swapping columns does not affect whether the condition 1. above is satisfied. Similarly, swapping rows does not affect whether the condition 2. above is satisfied. Therefore, the problem above can be decomposed into the following two independent problems:

• Row-Swapping Problem, where you need to determine if you can make \(A\) satisfy the condition 1. by swapping rows as many times as you want; and
• Column-Swapping Problem, where you need to determine if you can make \(A\) satisfy the condition 2. by swapping columns as many times as you want.

・Row-Swapping Problem

• First, we find the pair of minimum and maximum values \((m, M)\) of the elements in each row.
• Then, we sort the \(H\) rows in ascending order of \(m\) (with ties broken by ascending order of \(M\)).
• Finally, we check if the resulting \(A\) satisfies the condition 1.

・Column-Swapping Problem

Consider the following directed graph \(G\) that is obtained as follows, with \(W\) vertices corresponding to the \(W\) rows:

(★) for all pairs \((j, j')\) such that \(A_{i, j} \lt A_{i, j'}\), add an edge from vertex \(j\) to vertex \(j'\).

In other words, the graph \(G\) is a graph that has a directed edge from vertex \(j\) to vertex \(j'\) if and only if there is a constraint that:

“the \(j\)-th column in the initial state” should end up in the left of “the \(j'\)-th column in the initial state.”

Since we can rearrange the columns so that condition 2. is satisfied if and only if the directed graph \(G\) has a topological order, so it is sufficient to check if \(G\) is a DAG (Directed Acyclic Graph) to solve the problem.

However, the graph \(G\) above may contain a plethora of edges, so there is no hope of finishing within in the execution time limit. Instead, we construct a new directed graph \(G'\) equivalent to \(G\) above, that has a sufficiently few vertices and edges. Specifically, we replace the step (★) above in the construction of \(G\) by the following:

Let

\[A_{i, j_{1, 1}} = A_{i, j_{1, 2}} = \cdots = A_{i, j_{1, l_1}} \lt A_{i, j_{2, 1}} = A_{i, j_{2, 2}} = \cdots = A_{i, j_{2, l_2}} \lt \cdots \lt A_{i, j_{k, 1}} = A_{i, j_{k, 2}} = \cdots = A_{i, j_{1, l_k}} \]

be the elements in the \(i\)-th line, sorted in ascending order. We add new \((k-1)\) vertices \(v_{i, 1}, v_{i, 2}, \ldots, v_{i, k-1}\) to the graph and add directed edges as follows.

• From each of the \(l_1\) vertices \(j_{1, 1}, j_{1, 2}, \ldots, j_{1, l_1}\), add a directed edge to vertex \(v_{i, 1}\); and from vertex \(v_{i, 1}\), add a directed edge to each of the \(l_2\) vertices \(j_{2, 1}, j_{2, 2}, \ldots, j_{2, l_2}\).
• From each of the \(l_2\) vertices \(j_{2, 1}, j_{2, 2}, \ldots, j_{2, l_2}\), add a directed edge to vertex \(v_{i, 2}\); and from vertex \(v_{i, 2}\), add a directed edge to each of the \(l_2\) vertices \(j_{3, 1}, j_{3, 2}, \ldots, j_{3, l_3}\).
• \(\cdots\)
• From each of the \(l_{k-1}\) vertices \(j_{k-1, 1}, j_{k-1, 2}, \ldots, j_{k-1, l_{k-1}}\), add a directed edge to vertex \(v_{i, k-1}\); and from vertex \(v_{i, k-1}\), add a directed edge to each of the \(l_k\) vertices \(j_{k, 1}, j_{k, 2}, \ldots, j_{k, l_k}\).

Since this graph \(G'\) has \(O(HW)\) vertices and edges, we can meet the execution time limit.

If \(A\) contains \(0\)

Finally, we describe the case where \(A\) contains \(0\). To the contrary to the Problem Statement, we may assume that we first swap the rows and columns as many times as we want, and finally replace \(0\)’s with positive integers.

If the subsequence obtained by removing \(0\) from the sequence \(A' \coloneqq (A_{1, 1}, A_{1, 2} , \ldots, A_{1, W}, A_{2, 1} , A_{2, 2}, \ldots, A_{2, W}, A_{3, 1}, \ldots, A_{H-1, W}, A_{H, 1}, A_{H, 2}, \ldots, A_{H, W})\) is weakly monotonically increasing, then we can make \(A'\) weakly monotonically increasing by replacing \(0\)’s in \(A'\) with appropriate positive integers.

For example, if \(A' = (0, 0, 2, 0, 3, 4, 0, 0, 4, 0, 5, 0)\), we can let \(A' = (\red{1}, \red{1}, 2, \red{2}, 3, 4, \red{4}, \red{4}, 4, \red{4}, 5, 5, \red{5})\).

Therefore, we may solve in the same way as if \(A\) did not contain \(0\), by ignoring the elements of values \(0\).

The following is a sample code in C++ language.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int h, w;
int a[1000005];
vector<int> G[2000005];
bool used[2000005];
vector<int> topo;

void dfs(int v)
{
  used[v] = true;
  for(auto u : G[v]) if(!used[u]) dfs(u);
  topo.push_back(v);
}

int main(void)
{
  cin >> h >> w;
  for(int y = 1; y <= h; y++) for(int x = 1; x <= w; x++) cin >> a[(y-1)*w+(x-1)];
  
  vector<pair<int,int>> vec;
  for(int y = 1; y <= h; y++){
    int l = 1e9, r = -1e9;
    for(int x = 1; x <= w; x++){
      int v = a[(y-1)*w+(x-1)];
      if(v) l = min(l, v), r = max(r, v);
    }
    if(l <= r) vec.push_back({l, r});
  }
  sort(vec.begin(), vec.end());
  
  for(int i = 1; i < (int)vec.size(); i++){
    if(vec[i-1].second > vec[i].first){
      cout << "No"<< endl;
      return 0;
    }
  }
  
  for(int y = 1; y <= h; y++){
    vector<pair<int, int>> vec;
    for(int x = 1; x <= w; x++) if(a[(y-1)*w+(x-1)]) vec.push_back({a[(y-1)*w+(x-1)], x});
    sort(vec.begin(), vec.end());
    
    for(int i = 1; i < (int)vec.size(); i++){
      if(vec[i-1].first != vec[i].first){
        int v = w + vec[i-1].first;
        for(int j = i-1; j >= 0; j--){
          if(vec[j].first != vec[i-1].first) break;
          G[vec[j].second].push_back(v);
        }
        for(int j = i; j < (int)vec.size(); j++){
          if(vec[j].first != vec[i].first) break;
          G[v].push_back(vec[j].second);
        }
      }
    }
  }
  
  int n = w + h*w;
  for(int i = 1; i <= n; i++) if(!used[i]) dfs(i);
  reverse(topo.begin(), topo.end());
  
  for(int i = 1; i <= n; i++) used[i] = false;
  for(auto v : topo){
    used[v] = true;
    for(auto u : G[v]){
      if(used[u]){
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;

  return 0;
}