Fórmula de Euler

int N, h[750][750];
ll ans;
vector<pair<int, pi>> v;
 
int hsh(int a, int b) { return N * a + b; }
 
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
 
template <int SZ> struct DSU {
	int par[SZ], sz[SZ], measure[SZ];
	vi comp[SZ];
	DSU() { F0R(i, SZ) par[i] = i, sz[i] = 1, measure[i] = 1; }
	bool valid(int b, int c) { return b >= 0 && b < N && c >= 0 && c < N; }
	bool ok(int a, int b, int c) {
		if (!valid(b, c)) return 0;
		return par[hsh(b, c)] == a;
	}
	void addPoint(int x, pi t) {
		par[hsh(t.f, t.s)] = x;
		measure[x]++;
		F0R(i, 4) {
			if (ok(x, t.f + xd[i], t.s + yd[i])) {
				measure[x]--;
				int j = (i + 1) % 4;
				if (ok(x, t.f + xd[j], t.s + yd[j]) &&
				    ok(x, t.f + xd[j] + xd[i], t.s + yd[j] + yd[i]))
					measure[x]++;
			}
		}
		comp[x].pb(hsh(t.f, t.s));
	}
	void unite(pi x, pi y) {  // union-by-rank
		int X = hsh(x.f, x.s), Y = hsh(y.f, y.s);
		if (par[X] == par[Y]) return;
		X = par[X], Y = par[Y];
		if (sz(comp[X]) < sz(comp[Y])) swap(X, Y);
		trav(t, comp[Y]) addPoint(X, {t / N, t % N});
		comp[Y].clear();
	}
};
 
DSU<750 * 750> D;
bool ok[750][750];
 
void solve(int x, int y) {
	ok[x][y] = 1;
	F0R(i, 4) {
		int X = x + xd[i], Y = y + yd[i];
		if (X < 0 || X >= N || Y < 0 || Y >= N) continue;
		if (!ok[X][Y]) continue;
		D.unite({x, y}, {X, Y});
	}
}
 
int main() {
	setIO("valleys");
	re(N);
	F0R(i, N) F0R(j, N) {
		re(h[i][j]);
		v.pb({h[i][j], {i, j}});
		D.comp[hsh(i, j)].pb(hsh(i, j));
	}
	sort(all(v));
	F0R(i, sz(v)) {
		solve(v[i].s.f, v[i].s.s);
		pi p = v[i].s;
		int q = D.par[hsh(p.f, p.s)];
		if (D.measure[q] == 1) ans += sz(D.comp[q]);
	}
	cout << ans;
}