結果

問題 No.2743 Twisted Lattice
ユーザー Nzt3
提出日時 2024-04-12 22:01:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 518 ms / 3,000 ms
コード長 1,814 bytes
コンパイル時間 2,681 ms
コンパイル使用メモリ 216,920 KB
最終ジャッジ日時 2025-02-21 00:22:10
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr ll D_MAX=1e14;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int H,W,N;
  cin>>H>>W>>N;
  unordered_map<int,vector<ll>>P;
  vector<array<int,2>>Ps(N);
  for(int i=0;i<N;i++){
    int A,B;
    cin>>A>>B;
    P[B].push_back(A);
    Ps[i]={A,B};
  }
  for(auto &[key,val]:P){
    sort(val.begin(),val.end());
  }
  vector idx(0,0);
  for(auto i:P){
    idx.push_back(i.first);
  }
  sort(idx.begin(),idx.end());
  // for(int i:idx)cout<<i<<' ';cout<<'\n';
  vector dist_R(idx.size(),D_MAX),dist_L(idx.size(),D_MAX);
  ll dist_now=P[idx[0]][0]-1;
  for(int i=1;i<(int)idx.size();i++){
    dist_now+=idx[i]-idx[i-1];
    dist_L[i]=dist_now;
    dist_now=min(dist_now,P[idx[i]][0]-1);
  }
  dist_now=P[idx.back()][0]-1;
  for(int i=(int)idx.size()-2;i>=0;i--){
    dist_now+=idx[i+1]-idx[i];
    dist_R[i]=dist_now;
    dist_now=min(dist_now,P[idx[i]][0]-1);
  }
  for(int X=0;X<N;X++){
    ll h=Ps[X][0],w=Ps[X][1];
    int t=lower_bound(P[w].begin(),P[w].end(),h)-P[w].begin();
    ll ans=D_MAX;
    if(t+1<(int)P[w].size()){
      ans=min(ans,P[w][t+1]-h);
    }
    if(t>0){
      ans=min(ans,h-P[w][t-1]);
    }
    if(P.find(w-1)!=P.end()){
      int s=lower_bound(P[w-1].begin(),P[w-1].end(),h)-P[w-1].begin();
      if(s<(int)P[w-1].size()){
        ans=min(ans,P[w-1][s]);
      }
      if(s-1>=0){
        ans=min(ans,h);
      }
    }
    if(P.find(w+1)!=P.end()){
      int s=lower_bound(P[w+1].begin(),P[w+1].end(),h)-P[w+1].begin();
      if(s<(int)P[w+1].size()){
        ans=min(ans,P[w+1][s]);
      }
      if(s-1>=0){
        ans=min(ans,h);
      }
    }
    t=lower_bound(idx.begin(),idx.end(),w)-idx.begin();
    ans=min(ans,dist_L[t]+h-1);
    ans=min(ans,dist_R[t]+h-1);

    cout<<ans<<'\n';
  }
}
0