2和3挂了，5TLE了

#include <bits/stdc++.h>
using namespace std;
int n, m, mp[514][514];
bool map1[514], map2[114514];
struct node {
	int k;
	int l;
	int r;
} epty;
bool cmp(node a, node b)
{
	return a.l < b.l;
}
vector<node> p;
node connect(node a, node b)
{
	if (a.l + a.r > b.l + b.r)
		swap(a, b);
	if (a.r + 1 < b.l) {
		p.push_back(b);
		if (p[p.size() - 1].l == 114514191)
			p.pop_back();
		return a;
	}
	a.l = min(a.l, b.l);
	a.r = max(a.r, b.r);
	// cout<<a.l<<"~"<<a.r<<"\n";
	return a;
}
bool vis[514][514];
node dfs(int x, int y, int k)
{
	// cout<<x<<" "<<y<<"\n";
	node z;
	z = epty;
	z.k = k;
	bool flag = 0;
	if (y == n) {
		z.l = x;
		z.r = x;
		// cout<<x<<"~"<<"\n";
		flag = 1;
	}
	vis[x][y] = 1;
	if (x - 1 > 0 and vis[x - 1][y] == 0 and mp[x][y] > mp[x - 1][y]) {
		if (flag == 0) {
			z = dfs(x - 1, y, k);
			flag = 1;
		} else
			z = connect(z, dfs(x - 1, y, k));
	}
	if (x + 1 <= m and vis[x + 1][y] == 0 and mp[x][y] > mp[x + 1][y]) {
		if (flag == 0) {
			z = dfs(x + 1, y, k);
			flag = 1;
		} else
			z = connect(z, dfs(x + 1, y, k));
	}
	if (y + 1 <= n and vis[x][y + 1] == 0 and mp[x][y] > mp[x][y + 1]) {
		if (flag == 0) {
			z = dfs(x, y + 1, k);
			flag = 1;
		} else
			z = connect(z, dfs(x, y + 1, k));
	}
	if (y - 1 > 0 and vis[x][y - 1] == 0 and mp[x][y] > mp[x][y - 1]) {
		if (flag == 0) {
			z = dfs(x, y - 1, k);
			flag = 1;
		} else
			z = connect(z, dfs(x, y - 1, k));
	}
	return z;
}
int main()
{
	epty.k = -1;
	epty.l = 114514191;
	epty.r = 114514191;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> mp[j][i];
	for (int i = 1; i <= m; i++) {
		memset(vis, 0, sizeof vis);
		// cout<<i<<" ";
		p.push_back(dfs(i, 1, i)); // 从i开始流，统计流的范围
		if (p[p.size() - 1].l == 114514191)
			p.pop_back();
	}
	int sz = p.size();
	for (int i = 0; i < sz; i++)
		for (int j = 0; j < sz; j++)
			if (cmp(p[i], p[j]))
				swap(p[i], p[j]); // 排序
	// for(int i=0;i<sz;i++)
	// cout<<p[i].k<<" "<<p[i].l<<" "<<p[i].r<<"\n";

	// for (int i = 0; i < sz;i++)
	//	cout <<p[i].k<<" "<<p[i].l << " " << p[i].r<<"\n";
	int ans = 0, ri = 0;
	for (int i = 0; i < sz; i++) {
		while (ri < p[i].l - 1) {
			ri++;
			ans++;
		}
		ri = max(ri, p[i].r);
	}
	if (ri < m)
		ans += m - ri;
	if (ans > 0) {
		cout << 0 << "\n" << ans;
		return 0;
	}

	ri = 0;
	int t, r;
	while (ri < m) {
		t = -1, r = 0;
		for (int i = 0; i < sz and p[i].l <= ri + 1; i++) {
			if (map1[p[i].k] == 1 and map2[i] == 0) {
				map2[i] = 1;
				r = p[i].r;
				t = i;
			}
			if (p[i].r > r) {
				r = p[i].r;
				t = i;
			}
		}
		ri = r;
		if (map1[p[t].k] == 0) {
			map1[p[t].k] = 1;
			ans++;
		}
	}
	cout << 1 << "\n" << ans;
	return 0;
}