Submission #1871605

---

Source Code Expand

#include<cstdio>
#include<cstring>
#define LL long long
#define ll LL
#define N 1200000
#define INF 0x3f3f3f3f3f3f3f3f
LL n,m,x,y,ans,mn1,mn2,a[N],seg[2][N],seg0[2][N],seg1[2][N],tag[2][N];
 
ll min(ll x,ll y){ return x<y?x:y; }
ll max(ll x,ll y){ return x>y?x:y; }
ll abs(ll x){ return x>0?x:-x; }
void add(LL op,LL k){
	seg[op][1]+=k; seg0[op][1]+=k; seg1[op][1]+=k; tag[op][1]+=k;
}
 
void pushdown(LL op,LL x){
	tag[op][x<<1]+=tag[op][x]; tag[op][x<<1|1]+=tag[op][x];
	seg[op][x<<1]=min(INF,seg[op][x<<1]+tag[op][x]);
	seg0[op][x<<1]=min(INF,seg0[op][x<<1]+tag[op][x]);
	seg1[op][x<<1]=min(INF,seg1[op][x<<1]+tag[op][x]);
	seg[op][x<<1|1]=min(INF,seg[op][x<<1|1]+tag[op][x]);
	seg0[op][x<<1|1]=min(INF,seg0[op][x<<1|1]+tag[op][x]);
	seg1[op][x<<1|1]=min(INF,seg1[op][x<<1|1]+tag[op][x]);
	tag[op][x]=0;
}
 
void mdf(LL op,LL x,LL l,LL r,LL t,LL k){
	if (l==r){
		if (seg[op][x]>k){seg[op][x]=k; seg0[op][x]=k-t; seg1[op][x]=k+t;}
		return;
	}
	pushdown(op,x);
	LL mid=(l+r)>>1;
	if (t<=mid) mdf(op,x<<1,l,mid,t,k);
	if (t>mid) mdf(op,x<<1|1,mid+1,r,t,k);
	seg[op][x]=min(seg[op][x<<1],seg[op][x<<1|1]);
	seg0[op][x]=min(seg0[op][x<<1],seg0[op][x<<1|1]);
	seg1[op][x]=min(seg1[op][x<<1],seg1[op][x<<1|1]);
}
		
LL qry1(LL op,LL x,LL l,LL r,LL L,LL R){
	if (l>=L && r<=R){
		return seg0[op][x];
	}
	LL mid=(l+r)>>1,tmp=INF;
	pushdown(op,x);
	if (L<=mid) tmp=min(tmp,qry1(op,x<<1,l,mid,L,R));
	if (R>mid) tmp=min(tmp,qry1(op,x<<1|1,mid+1,r,L,R));
	return tmp;
}
 
LL qry2(LL op,LL x,LL l,LL r,LL L,LL R){
	if (l>=L && r<=R){
		return seg1[op][x];
	}
	LL mid=(l+r)>>1,tmp=INF;
	pushdown(op,x);
	if (L<=mid) tmp=min(tmp,qry2(op,x<<1,l,mid,L,R));
	if (R>mid) tmp=min(tmp,qry2(op,x<<1|1,mid+1,r,L,R));
	return tmp;
}
 
int main(){
	scanf("%lld%lld%lld%lld",&n,&m,&x,&y);
	memset(seg,0x3f,sizeof seg);
	memset(seg0,0x3f,sizeof seg0);
	memset(seg1,0x3f,sizeof seg1);
	mdf(0,1,1,n,x,0); mdf(1,1,1,n,y,0);
	for (LL i=1;i<=m;i++){
		scanf("%lld",&a[i]);
		mn1=mn2=INF;
		mn1=qry1(0,1,1,n,1,a[i])+a[i];
		mn1=min(mn1,qry2(0,1,1,n,a[i],n)-a[i]);
		mn2=qry1(1,1,1,n,1,a[i])+a[i];
		mn2=min(mn2,qry2(1,1,1,n,a[i],n)-a[i]);
		add(0,abs(a[i]-(i==1?y:a[i-1])));
		add(1,abs(a[i]-(i==1?x:a[i-1])));
		mdf(0,1,1,n,i==1?x:a[i-1],mn2); mdf(1,1,1,n,i==1?y:a[i-1],mn1);
	}
	printf("%lld\n",min(seg[0][1]+tag[0][1],seg[1][1]+tag[1][1]));
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:64:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld",&n,&m,&x,&y);
                                       ^
./Main.cpp:70:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^

Judge Result