結果

問題 No.2743 Twisted Lattice
ユーザー 0214sh70214sh7
提出日時 2024-04-21 07:11:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,477 bytes
コンパイル時間 3,051 ms
コンパイル使用メモリ 226,588 KB
実行使用メモリ 57,984 KB
最終ジャッジ日時 2024-04-21 07:12:03
合計ジャッジ時間 13,653 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 991 ms
57,984 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> PP;
// #define MOD 1000000007
#define MOD 998244353
#define INF 2305843009213693951
//#define INF 810114514
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)
#define ORREP(i,n) for(ll i=(n);i>=1;--i)
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define GOODBYE do { cout << "-1" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug true
#define debug2 false


int main(void){
    //cin.tie(nullptr);
    //ios::sync_with_stdio(false);

    ll H,W,N;
    cin >> H >> W >> N;
    vector<ll> A(N),B(N);
    REP(i,N){
        cin >> A[i] >> B[i];
    }
    
    vector<ll> Ans(N,INF);
    map<pair<ll,ll>,ll> index;
    REP(i,N){
        index[{A[i],B[i]}] = i;
    }
    
    // 同じ列で探す
    map<ll,vector<ll>> T;
    REP(i,N){
        T[B[i]].push_back(A[i]);
    }
    
    for(auto p:T){
        vector<ll> v = p.second;
        REP(i,-1+v.size()){
            ll k1 = index[{v[i]  ,p.first}];
            ll k2 = index[{v[i+1],p.first}];
            Ans[k1] = min(Ans[k2],abs(v[i+1]-v[i]));
            Ans[k2] = min(Ans[k1],abs(v[i+1]-v[i]));
        }
    }
    
    // 一つとなりの列で探す
    
    auto it = T.begin();
    auto it2 = it;it2++;
    while(it2 != T.end()){
        
        if((it->first)+1 != (it2->first)){
            it++;it2++;
            continue;
        }
        
        vector<ll> u = it->second, v = it2->second;
        ll ux = (it->first) , vx = (it2->first);
        // cout << ux MM vx << endl;
        
        u.push_back(-INF); u.push_back(INF);
        v.push_back(-INF); v.push_back(INF);
        sort(ALL(u)); sort(ALL(v));
        
        // cout << "! ";for(ll e:u)cout << e << " ";cout << endl;
        // cout << "! ";for(ll e:v)cout << e << " ";cout << endl;
        REP(_,2){
            REP(i,u.size()){
                if(i==0 || i+1==u.size())continue;
                auto it3 = lower_bound(ALL(v),u[i]);
                ll k1 = index[{u[i],ux}];
                if(*it3!=INF){
                    ll vy = *it3;
                    ll k2 = index[{vy,vx}];
                    ll c = min(u[i],vy)*abs(ux-vx) + abs(u[i]-vy);
                    // cout << "? " << u[i] MM ux MM vy MM vx << " " << c << endl;
                    Ans[k1] = min(Ans[k1],c);
                    Ans[k2] = min(Ans[k2],c);
                }
                it3--;
                if(*it3!=-INF){
                    ll vy = *it3;
                    ll k2 = index[{vy,vx}];
                    ll c = min(u[i],vy)*abs(ux-vx) + abs(u[i]-vy);
                    // cout << "? " << u[i] MM ux MM vy MM vx << " " << c << endl;
                    Ans[k1] = min(Ans[k1],c);
                    Ans[k2] = min(Ans[k2],c);
                }
            }
            swap(u,v);
        }
        
        it++;it2++;
    }
    
    // 遠いところ
    map<ll,ll> Mp;
    REP(i,N){
        Mp[B[i]] = INF;
    }
    REP(i,N){
        Mp[B[i]] = min(Mp[B[i]],A[i]-1);
    }
    
    // for(auto p:Mp)cout << p.first MM p.second << endl;
    vector<ll> Le(Mp.size(),INF);
    auto Re = Le;
    
    
    ll now = 0;
    for(auto p:Mp){
        Le[now] = -p.first+p.second;
        Re[now] = p.first+p.second;
        now++;
    }
    
    REP(i,-1+Mp.size()){
        Le[i+1] = min(Le[i+1],Le[i]);
    }
    RREP(i,-1+Mp.size()){
        Re[i] = min(Re[i],Re[i+1]);
    }
    
    // map<ll,ll> ML,MR;
    // now = 0;
    // for(auto p:Mp){
    //     ML[p.first] = Le[now];
    //     MR[p.first] = Re[now];
    //     now++;
    // }
    
    now = 0;
    for(auto p:T){
        vector<ll> v = p.second;
        ll x = p.first;
        
        REP(i,v.size()){
            ll k = index[{v[i],x}];
            if(now!=0){
                ll c = Le[now-1] + x + v[i] -1;
                Ans[k] = min(Ans[k],c);
            }
            if(now+1!=Mp.size()){
                ll c = Re[now+1] - x + v[i] -1;
                Ans[k] = min(Ans[k],c);
            }
        }
        
        now++;
    }
    
    // REP(i,Mp.size()){cout << Le[i] << " ";}cout << endl;
    // REP(i,Mp.size()){cout << Re[i] << " ";}cout << endl;
    
    
    
    
    REP(i,N){
        cout << Ans[i] << endl;
    }
    
    return 0;
    
}
0