Submission #75708067

---

Source Code Expand

#include<bits/stdc++.h>
#define int long long
#define inf 1e18
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)

using namespace std;
int h,w,n;
struct mat{
    int a[4][4];
    mat(){rep(i,0,3)rep(j,0,3)a[i][j]=inf;}
};
mat mul(mat x,mat y){
    mat z;
    rep(i,0,3)rep(j,0,3)rep(k,0,3)z.a[i][j]=min(z.a[i][j],x.a[i][k]+y.a[k][j]);
    return z;
}
mat p[35];
struct vec{
    int a[4];
    vec(){rep(i,0,3)a[i]=inf;}
};
vec mul(vec x,mat y){
    vec z;
    rep(i,0,3)rep(j,0,3)z.a[j]=min(z.a[j],x.a[i]+y.a[i][j]);
    return z;
}
vec adv(vec x,int d){
    if(d>1){
        int q=d-1;
        rep(k,0,30)if((q>>k)&1)x=mul(x,p[k]);
    }
    vec z;
    int add[4]={2,2,2,4};
    rep(i,0,3)z.a[i]=x.a[i]+add[i];
    return z;
}
void get_e(vector<int>&c,int&l,int&r,int&lr){
    c.erase(unique(c.begin(),c.end()),c.end());
    int u=c.front(),v=c.back(),s=c.size();
    l=2*(v-1);r=2*(w-u);lr=min(l,r);
    rep(i,0,s-2)lr=min(lr,2*(c[i]-1)+2*(w-c[i+1]));
    return;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>h>>w>>n;
    vector<pair<int,int>> pts;
    rep(i,1,n){
        int R,C;cin>>R>>C;
        pts.push_back({R,C});
    }
    pts.push_back({1,1});
    sort(pts.begin(),pts.end());
    vector<int> rv;
    vector<vector<int>> cols;
    for(auto&pt:pts){
        if(rv.empty()||rv.back()!=pt.first){
            rv.push_back(pt.first);
            cols.push_back({pt.second});
        }else{
            cols.back().push_back(pt.second);
        }
    }
    int l,r,lr;
    get_e(cols.back(),l,r,lr);
    if(rv.back()==1){
        cout<<l<<'\n';
        return 0;
    }
    int ip[4][4]={
        {2, 2*w, w+1, 2},
        {2*w, 2, w+1, 2},
        {w+1, w+1, 2, w+1},
        {2*w, 2*w, w+1, 4}
    };
    rep(i,0,3)rep(j,0,3)p[0].a[i][j]=ip[i][j];
    rep(i,1,30)p[i]=mul(p[i-1],p[i-1]);
    vec dp;
    dp.a[0]=l;dp.a[1]=r;dp.a[2]=w-1;dp.a[3]=lr;
    int m=rv.size();
    per(i,m-1,1){
        int cur=rv[i],pre=rv[i-1],d=cur-pre;
        dp=adv(dp,d);
        if(pre>1){
            get_e(cols[i-1],l,r,lr);
            int c1=w-1,c2=2*w-2;
            int it[4][4]={
                {l,  c2, c1, lr},
                {c2, r,  c1, lr},
                {c1, c1, lr, c1},
                {c2, c2, c1, lr}
            };
            mat t;
            rep(u,0,3)rep(v,0,3)t.a[u][v]=it[u][v];
            dp=mul(dp,t);
        }else{
            get_e(cols[0],l,r,lr);
            cout<<min({dp.a[0]+l,dp.a[1]+2*w-2,dp.a[2]+w-1,dp.a[3]+2*w-2})<<'\n';
            return 0;
        }
    }
    return 0;
}

Submission Info

Judge Result