Submission #1693275

---

Source Code Expand

#include<bits/stdc++.h>
#define N 200005
#define ls x<<1,l,mid
#define rs x<<1|1,mid+1,r
#define int long long
using namespace std;
int n,q,ps;
int w[N];
int a[N*4],b[N*4],lazy[N*4];
void push_down(int x)
{
    int l=x*2,r=x*2+1,z=lazy[x];
    a[l]+=z;b[l]+=z;
    a[r]+=z;b[r]+=z;
    lazy[l]+=z;lazy[r]+=z;
    lazy[x]=0;
}
void push_up(int x)
{
    a[x]=min(a[x<<1],a[x<<1|1]);
    b[x]=min(b[x<<1],b[x<<1|1]);
}
int qur1(int x,int l,int r,int ll,int rr)
{
    if(l>=ll&&r<=rr)return a[x];
    push_down(x);
    int mid=(l+r)>>1;
    if(ll>mid)return qur1(rs,ll,rr);
    if(rr<=mid)return qur1(ls,ll,rr);
    return min(qur1(ls,ll,rr),qur1(rs,ll,rr));
}
int qur2(int x,int l,int r,int ll,int rr)
{
    if(l>=ll&&r<=rr)return b[x];
    push_down(x);
    int mid=(l+r)>>1;
    if(ll>mid)return qur2(rs,ll,rr);
    if(rr<=mid)return qur2(ls,ll,rr);
    return min(qur2(ls,ll,rr),qur2(rs,ll,rr));
}
void add(int x,int l,int r,int pos,int z)
{
    if(l==r)
    {
        a[x]=min(a[x],z-l);
        b[x]=min(b[x],z+l);
        return ;
    }
    int mid=(l+r)>>1;
    push_down(x);
    if(pos<=mid)add(ls,pos,z);
    else add(rs,pos,z);
    push_up(x);
}
int ans=1LL<<60;
void dfs(int x,int l,int r)
{
    if(l==r)
    {
        ans=min(ans,b[x]-l);
        return ;
    }
    int mid=(l+r)>>1;
    push_down(x);
    dfs(ls);dfs(rs);
}
signed main()
{
    scanf("%lld%lld%lld%lld",&n,&q,&w[0],&ps);
    memset(a,0x3f,sizeof(a));memset(b,0x3f,sizeof(b));add(1,1,n,ps,0);
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&ps);w[i]=ps;
        int tmp=min(qur2(1,1,n,ps,n)-ps,ps+qur1(1,1,n,1,ps));
        int tp=abs(ps-w[i-1]);
        lazy[1]+=tp;a[1]+=tp;b[1]+=tp;
        add(1,1,n,w[i-1],tmp);
    }
    dfs(1,1,n);
    cout<<ans<<endl;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:73:23: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
         scanf("%d",&ps);w[i]=ps;
                       ^
./Main.cpp:69:46: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld%lld",&n,&q,&w[0],&ps);
                                              ^
./Main.cpp:73:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&ps);w[i]=ps;
                        ^

Judge Result