Submission #55813732

---

Source Code Expand

/*
Author: rnishiura
Date: 24-06-15
Description: template
*/

#define ATCODER_
#include <bits/stdc++.h>
#ifdef ATCODER_
#include <atcoder/all>
#endif
#define _GLIBCXX_DEBUG
#define rep(x, n)      for(ll x=0; x<n; x++)
#define repi(x, a, b)  for(ll x=a; x<b; x++)
#define rrep(x, n)     for(ll x=n-1; x>=0; x--)
#define rrepi(x, a, b) for(ll x=b-1; x>=a; x--)
#define SQ(z) ((z)*(z))
#define contains(x, a) ((a).find(x) != (a).end())
#define all(a) (a).begin(), (a).end()
#define sum(a)  (accumulate(all(a), 0LL))
#define mini(a) (min_element(all(a)) - (a).begin())
#define maxi(a) (max_element(all(a)) - (a).begin())
#define mine(a) (*min_element(all(a)))
#define maxe(a) (*max_element(all(a)))
#define lowb(x, a) (lower_bound(all(a), (x)) - (a).begin())
#define uppb(x, a) (upper_bound(all(a), (x)) - (a).begin())
#define divl(n, m)  ((n+m)/(m)) 
#define divle(n, m) ((n+m-1)/(m)) 
#define divse(n, m) ((n)/(m)) 
#define divs(n, m)  ((n-1)/(m)) 
#define bstoi(s)  stoi((s), nullptr, 2)
#define MOD 998244353
#define PI 3.14159265358979323846
#define inf (1LL << 61)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define POS  fi
#define COST se
#define endl '\n'
#define unordered_multiset multiset

#define print(z)        { cout << (z) << endl;              }
#define print2(y, z)    { cout << (y) << ' '; print(z);     }
#define print3(x, y, z) { cout << (x) << ' '; print2(y, z); }
#define debug(z)        { if(DEBUG) print(z);        }
#define debug2(y, z)    { if(DEBUG) print2(y, z);    }
#define debug3(x, y, z) { if(DEBUG) print3(x, y, z); }

#ifdef ATCODER_
using namespace atcoder;
using mint = modint998244353;
#endif

using namespace std;
using ll  = long long;
using v   = vector<ll>;
using vv  = vector<v>;
using vp  = vector<pair<ll, ll>>;
using vvp = vector<vp>;

template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> pair<T,T> operator*(pair<T,T> a,         U b){return mp(a.first*b      , a.second*b);}
template<typename T, typename U> pair<T,T> operator/(pair<T,T> a,         U b){return mp(a.first/b      , a.second/b);}
template<typename T, typename U> pair<T,T> operator%(pair<T,T> a,         U b){return mp(a.first%b      , a.second%b);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

void build_sea(vv &s) {
  ll w = s[0].size();
  v t(w+2, 0);
  for(auto& ss: s) { ss.insert(ss.begin(), 0); ss.pb(0); }
  s.insert(s.begin(), t);
  s.pb(t);
}

// const int DEBUG = 1;
const int DEBUG = 0;

void solve() {
  ll h, w, y; cin >> h >> w >> y;
  vv a(h, v(w)); cin >> a;
  vvp ha(100001);
  rep(i, h) {
    rep(j, w) {
      ha[a[i][j]].pb({i+1, j+1});
    }
  }

  build_sea(a);

  ll ans = h*w;
  vector<vector<bool>> sea(h+2, vector<bool>(w+2, false));
  rep(i, h+2) sea[i][0] = true, sea[i][w+1] = true;
  rep(i, w+2) sea[0][i] = true, sea[h+1][i] = true;

  // for(auto e: sea) print(e);
  // for(auto e: sea) {
  //   for(auto f: e) {
  //     cout << int(f) << " ";
  //   }
  //   print("");
  // }

  vp dir = {{1,0},{0,1},{-1,0},{0,-1}};
  repi(i, 1, y+1) {
    vp from = ha[i];
    while(true) {
      // print2(i, from.size());
      if(!from.size()) break;
      vp to;
      for(auto f: from) {
        if(
          sea[f.fi+1][f.se] ||
          sea[f.fi][f.se+1] ||
          sea[f.fi-1][f.se] ||
          sea[f.fi][f.se-1]
        ) {
          if(!sea[f.fi][f.se]) ans--;
          sea[f.fi][f.se] = true;
        } 
        if(!sea[f.fi][f.se]) continue;
        for(auto d: dir) {
          // if(f.fi+d.fi == 3 & f.se+d.fi)
          if(a[f.fi+d.fi][f.se+d.se] <= i && !sea[f.fi+d.fi][f.se+d.se]) {
            to.pb({f.fi+d.fi, f.se+d.se});
            sea[f.fi+d.fi][f.se+d.se] = true;
            ans--;
          }
        }
      }
      from = vp(all(to));
      // print(to);
    }
    print(ans);
    // print(i);
    // for(auto e: sea) {
    //   for(auto f: e) {
    //     cout << int(f) << " ";
    //   }
    //   print("");
    // }
  }

}

int main(void) {
  debug("DEBUG MODE IS ON");

  cin.tie(nullptr); ios::sync_with_stdio(false);
  
  ll t = 1; // cin >> t;
  rep(i, t) solve();

  debug("DEBUG MODE IS ON");
}

Submission Info

Judge Result