Submission #55803991

---

Source Code Expand

#include <bits/stdc++.h>
// #include "prettyprint.hpp"
#define fastio                 \
	ios::sync_with_stdio(false); \
	cin.tie(0)
#define ll long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<array<ll,2>, null_type, less<array<ll,2>>, rb_tree_tag, tree_order_statistics_node_update>

template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>>
{
	static_assert(D >= 1, "Vector dimension must be greater than zero!");
	template <typename... Args>
	Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...))
	{
	}
};
template <typename T>
struct Vec<1, T> : public vector<T>
{
	Vec(int n = 0, const T &val = T()) : vector<T>(n, val)
	{
	}
};

// Code begins here

const ll M = 1000000007LL;
const ll INF = 1e18 + 10;

template <typename T>
void maxa(T &v, const T &x)
{
	v = max(v, x);
}

template <typename T>
void mina(T &v, const T &x)
{
	v = min(v, x);
}

template <typename T>
void madd(T &v, const T &x)
{
	v = (v + x);
	v %= M;
}

const int mxn = 1e6 +10;

ll pw(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = (res * a) % M;
		a = (a * a) % M;
		b >>= 1;
	}
	return res;
}

void solve(){
	int h,w,y;
	cin >> h >> w >> y;
	Vec<2, int> a(h, w);
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin >> a[i][j];
		}
	}
	set<array<ll,3>> q;
	Vec<2, ll> dist(h, w, INF);
	for (int i=0;i<h;++i){
		for (int j=0;j<w;++j){
			if (i==0 || i==h-1 || j==0 || j==w-1){
				dist[i][j] = a[i][j];
				q.insert({dist[i][j], i, j});
			}
		}
	}
	vector<pair<int,int>> dir = {{-1,0}, {1,0}, {0,-1}, {0,1}};
	while (!q.empty()){
		auto [d, i, j] = *q.begin();
		q.erase(q.begin());
		for (auto [di, dj] : dir){
			int ni2 = i+di;
			int nj2 = j+dj;
			if (ni2<0 || ni2>=h || nj2<0 || nj2>=w) continue;
			ll nd = max(d, (ll)a[ni2][nj2]);
			if (dist[ni2][nj2] > nd){
				q.erase({dist[ni2][nj2], ni2, nj2});
				dist[ni2][nj2] = nd;
				q.insert({dist[ni2][nj2], ni2, nj2});
			}
		}
	}
	vector<ll> b;
	for (int i=0;i<h;++i){
		for (int j=0;j<w;++j){
			b.push_back(dist[i][j]);
		}
	}
	sort(b.begin(), b.end());
	for (int i=1;i<=y;++i){
		int idx = upper_bound(b.begin(), b.end(), i) - b.begin();
		cout << h*w-idx << "\n";
	}
}


int main()
{
	fastio;
	// freopen("in.txt","r",stdin);
	// int t;
	// cin >> t;
	// while (t--)
	solve();
}

Submission Info

Judge Result