Submission #2231787

---

Source Code Expand

#include <bits/stdc++.h>
const int maxn=1e5+10,mod=1e9+7;
const long long inf=1e10;
using namespace std;
int n,m,k,t;
struct node
{
    long long x,l,r,tag;
    node operator+(const node&p)const
    {
        node ret;
        ret.x=min(x,p.x);
        ret.l=min(l,p.l);
        ret.r=min(r,p.r);
        ret.tag=0;
        return ret;
    }
}tr[maxn<<2];
void pup(int rt){tr[rt]=tr[rt<<1]+tr[rt<<1|1];}
void pdw(int rt)
{
    tr[rt<<1].x+=tr[rt].tag;
    tr[rt<<1].l+=tr[rt].tag;
    tr[rt<<1].r+=tr[rt].tag;
    tr[rt<<1].tag+=tr[rt].tag;
    tr[rt<<1|1].x+=tr[rt].tag;
    tr[rt<<1|1].l+=tr[rt].tag;
    tr[rt<<1|1].r+=tr[rt].tag;
    tr[rt<<1|1].tag+=tr[rt].tag;
    tr[rt].tag=0;
}
node query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)return tr[rt];
    int mid=l+r>>1;
    if(tr[rt].tag)pdw(rt);
    node ret={-1,-1,-1,0};
    if(L<=mid)ret=query(L,R,l,mid,rt<<1);
    if(mid+1<=R)
    {
        node tmp=query(L,R,mid+1,r,rt<<1|1);
        if(ret.x==-1)ret=tmp;
        else ret=ret+tmp;
    }
    return ret;
}
void upd1(int L,int R,long long w,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        tr[rt].tag+=w;
        tr[rt].x+=w;
        tr[rt].l+=w;
        tr[rt].r+=w;
        return;
    }
    int mid=l+r>>1;
    if(tr[rt].tag)pdw(rt);
    if(L<=mid)upd1(L,R,w,l,mid,rt<<1);
    if(mid+1<=R)upd1(L,R,w,mid+1,r,rt<<1|1);
    pup(rt);
}
void upd2(int x,long long w,int l,int r,int rt)
{
    if(x==l&&x==r)
    {
        tr[rt]=node{w,w-l,w+l,0};
        return;
    }
    if(tr[rt].tag)pdw(rt);
    int mid=l+r>>1;
    if(x<=mid)upd2(x,w,l,mid,rt<<1);
    else upd2(x,w,mid+1,r,rt<<1|1);
    pup(rt);
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        tr[rt]=node{inf,inf,inf,0};
        return;
    }
    int mid=l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pup(rt);
}
int main()
{
    int i,j;
    int q,a,b,pos;
    scanf("%d%d%d%d%d",&n,&q,&a,&b,&pos);
    build(1,n,1);
    upd2(a,abs(pos-b),1,n,1);
    upd2(b,abs(pos-a),1,n,1);
    //printf("***%lld\n",tr[1].x);
    q--;
    while(q--)
    {
        scanf("%d",&j);
        long long ret=1e18;
        if(j>=1)
        {
            node p=query(1,j,1,n,1);
            ret=min(ret,j+p.l);
        }
        if(j<n)
        {
            node p=query(j+1,n,1,n,1);
            ret=min(ret,p.r-j);
        }
        upd1(1,n,abs(j-pos),1,n,1);
        node x=query(pos,pos,1,n,1);
        if(x.x>ret)upd2(pos,ret,1,n,1);
        pos=j;
        //printf("***%lld\n",tr[1].x);
    }
    printf("%lld\n",tr[1].x);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:92:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d",&n,&q,&a,&b,&pos);
                                         ^
./Main.cpp:100:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&j);
                       ^

Judge Result