记录编号	605123	评测结果	AAWAAAAAAA
题目名称	521.[NOIP 2010]引水入城	最终得分	90
用户昵称	xpb	是否通过	未通过
代码语言	C++	运行时间	0.295 s
提交时间	2025-08-14 11:36:25	内存使用	5.22 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, m, h[N][N], L[N][N], R[N][N];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
struct P {
    int x, y, h;
    bool operator<(const P& o) const { return h < o.h; }
};

struct I {
    int l, r;
    bool operator<(const I& o) const { return l < o.l; }
};

int main() {
    freopen("flow.in", "r", stdin);
    freopen("flow.out", "w", stdout);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> h[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (i == n - 1) L[i][j] = R[i][j] = j;
            else L[i][j] = N, R[i][j] = -1;
    vector<P> ps;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            ps.push_back({i, j, h[i][j]});
    sort(ps.begin(), ps.end());
    for (auto p : ps) {
        int x = p.x, y = p.y;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || h[nx][ny] >= h[x][y]) continue;
            L[x][y] = min(L[x][y], L[nx][ny]);
            R[x][y] = max(R[x][y], R[nx][ny]);
        }
    }
    vector<bool> cov(m);
    vector<I> ivs;
    for (int j = 0; j < m; j++)
        if (L[0][j] <= R[0][j]) {
            for (int k = L[0][j]; k <= R[0][j]; k++) cov[k] = true;
            ivs.push_back({L[0][j], R[0][j]});
        }
    int cnt = 0;
    for (int j = 0; j < m; j++) if (!cov[j]) cnt++;
    if (cnt) {
        cout << "0\n" << cnt << endl;
    } else {
        sort(ivs.begin(), ivs.end());
        int cur = -1, res = 0;
        while (cur < m - 1) {
            int mr = cur;
            for (auto iv : ivs)
                if (iv.l <= cur + 1) mr = max(mr, iv.r);
            if (mr == cur) break;
            res++;
            cur = mr;
        }
        cout << "1\n" << res << endl;
    }

    return 0;
}