結果
問題 | No.2743 Twisted Lattice |
ユーザー | Nzt3 |
提出日時 | 2024-04-12 22:01:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 456 ms / 3,000 ms |
コード長 | 1,814 bytes |
コンパイル時間 | 2,708 ms |
コンパイル使用メモリ | 218,140 KB |
実行使用メモリ | 28,280 KB |
最終ジャッジ日時 | 2024-04-12 22:03:53 |
合計ジャッジ時間 | 7,912 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 427 ms
28,280 KB |
testcase_01 | AC | 171 ms
7,328 KB |
testcase_02 | AC | 124 ms
7,936 KB |
testcase_03 | AC | 428 ms
28,032 KB |
testcase_04 | AC | 451 ms
28,260 KB |
testcase_05 | AC | 452 ms
28,156 KB |
testcase_06 | AC | 456 ms
28,160 KB |
testcase_07 | AC | 449 ms
28,028 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
ソースコード
#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'; } }