E. Correct Placement

1700
  • Quiz
  • AC
  • 解説
    • 座圧したりセグ木使ったり色々解法はあるようですが、mapを使った解法を紹介します
    • (width, height)は横長で揃えておく
    • (width, height, index)のデータをwidthの昇順ソートし、小さい順に見ていく
    • 今見ているデータより前に出てきたデータは現在のwidth以下である（ので、あとはheightだけに注目すればいい）
    • 現在のwidth「未満」の人の中での最小高さ（とその人のindex）を持っておけば、その人は小さい（枠に収まる）

f:id:peroon:20210125064438p:plain

void solve(){
  ll N;
  cin>>N;

  // width => (height, index)
  map<ll, vector<PII>> mp;
  
  rep(i,N){
    ll w,h;cin>>w>>h;
    // assume w >= h
    if(h>w)swap(w,h);
    mp[w].push_back({h,i});
  }
  
  VI Ans(N,-2);
  ll min_height=inf;
  ll min_height_index=-1;
  for(auto pa : mp){
    ll w = pa.first;

    ll local_min_height=inf;
    ll local_min_height_idx=-1;
    for(auto h_i : pa.second){
      ll h = h_i.first;
      ll idx = h_i.second;
      if(min_height<h){
        // found!
        Ans[idx]=min_height_index;
      }
      if(chmin(local_min_height,h)){
        local_min_height_idx = idx;
      }
    }

    // finally, update for next width
    if(chmin(min_height, local_min_height)){
      min_height_index = local_min_height_idx;
    }
  }
  print_vector(Ans,1);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; cin>>N;
    while(N--)solve();
    
    return 0;
}