マスに書かれた数字が大きいところから答えを決めていく. 大きい数字のマスの答えが確定していれば, (同じ行または同じ列の)小さい数字のマスの答えが確定する.
遷移するために持っておくべきものを求める. 今答えを決めようとしているマスを \( (r,c) \) とする.
- \(mr\) := \(r\) 行目において,既に決まっている答えの最大値
- \(mc\) := \(c\) 行目において,既に決まっている答えの最大値
マス \( (r,c) \) の答えは,\(max(mr, mc) + 1\) となる. ただし,同じ行,同じ列に.同じ数字の書かれたマスが複数ある場合, 同時に答えを決めないといけない. そうしないと,同じ数字の中でも後から決めた方の path が長くなってしまうから. -->
int main() {
ll h,w,n; cin >> h >> w >> n;
vll r(n) , c(n), a(n);
map<ll,ll> mr, mc;
rep(i,n){
cin >> r[i] >> c[i] >> a[i];
r[i]--, c[i]--;
pie[i] = {r[i], c[i]};
mp[-a[i]].emplace_back(i);
mr[r[i]] = -1;
mc[c[i]] = -1;
}
vll ans(n,-1);
for(auto [x,v]:mp){
for(int i: v){
auto [r,c] = pie[i];
ll now = max(mr[r], mc[c]);
chmax(ans[i], now);
}
for(int i: v){
auto [r,c] = pie[i];
chmax(ans[i], ans[i] + 1);
chmax(mr[r], ans[i]);
chmax(mc[c], ans[i]);
}
}
rep(i,n) cout << ans[i] << endl;
return 0;
}