Submission #3213896

---

Source Code Expand

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int getint()
{
    int i=0,f=1;char c;
    for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());
    if(c=='-')c=getchar(),f=-1;
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
    return i*f;
}
const int N=200005,mod=1e9+7;
const ll INF=1e18;
int n,m,A,B,q[N];
ll f[N<<2],g[N<<2],h[N<<2],tag[N<<2];
void add(int k,ll v){if(f[k]!=INF)f[k]+=v,g[k]+=v,h[k]+=v,tag[k]+=v;}
void pushdown(int k){add(k<<1,tag[k]),add(k<<1|1,tag[k]);tag[k]=0;}
void update(int k)
{
    f[k]=min(f[k<<1],f[k<<1|1]);
    g[k]=min(g[k<<1],g[k<<1|1]);
    h[k]=min(h[k<<1],h[k<<1|1]);
}
void build(int k,int l,int r)
{
    f[k]=g[k]=h[k]=INF;
    if(l==r)return;
    int mid=l+r>>1;
    build(k<<1,l,mid),build(k<<1|1,mid+1,r);
}
void chkmin(int k,int l,int r,int p,ll v)
{
    if(l==r)
    {   
        if(v<f[k])f[k]=v,g[k]=v-l,h[k]=v+l;
        return;
    }
    if(tag[k])pushdown(k);
    int mid=l+r>>1;
    p<=mid?chkmin(k<<1,l,mid,p,v):chkmin(k<<1|1,mid+1,r,p,v);
    update(k);
}
ll query(int k,int l,int r,int x,int y,int op)
{
    if(x>y)return INF;
    if(x<=l&&r<=y)return op?h[k]:g[k];
    if(tag[k])pushdown(k);
    int mid=l+r>>1;
    if(y<=mid)return query(k<<1,l,mid,x,y,op);
    else if(x>mid)return query(k<<1|1,mid+1,r,x,y,op);
    else return min(query(k<<1,l,mid,x,mid,op),query(k<<1|1,mid+1,r,mid+1,y,op));
}
int main()
{
    //freopen("lx.in","r",stdin);
    n=getint(),m=getint(),A=getint(),B=getint();
    build(1,1,n);
    for(int i=1;i<=m;i++)q[i]=getint();
    q[0]=B;chkmin(1,1,n,A,0);
    for(int i=1;i<=m;i++)
    {
        ll tmp=min(query(1,1,n,1,q[i],0)+q[i],query(1,1,n,q[i]+1,n,1)-q[i]);
        add(1,abs(q[i]-q[i-1]));chkmin(1,1,n,q[i-1],tmp);
    }
    cout<<f[1]<<'\n';
    return 0;
}

Submission Info

Judge Result