Submission #26776528

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int H, W, N;
multiset<int> row[200005], col[200005];
struct Node {
  int r, c, x, i;
};
map<int, vector<Node>> mp;
int ans[200005];
int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  cin >> H >> W >> N;
  vector<Node> a;
  for(int i=0;i<N;++i) {
    int r, c, x; cin >> r >> c >> x;
    a.push_back({r, c, x, i});
    if (!mp.count(x)) mp[x] = vector<Node>();
    mp[x].push_back({r, c, x, i});
  }
  for(auto it=mp.rbegin();it!=mp.rend();++it) {
    for(auto a:it->second) {
      int r = a.r;
      int c = a.c;
      int idx = a.i;
      if (!row[r].empty()) ans[idx] = max(ans[idx], *row[r].rbegin() + 1);
      if (!col[c].empty()) ans[idx] = max(ans[idx], *col[c].rbegin() + 1);
    }
    for(auto a:it->second) {
      int r = a.r;
      int c = a.c;
      int idx = a.i;
      row[r].insert(ans[idx]);
      col[c].insert(ans[idx]);
    }
  }
  for(int i=0;i<N;++i) cout << ans[i] << '\n';
}

Submission Info

Judge Result