Submission #1871603
Source Code Expand
#include<cstdio> #include<cstring> #define LL long long #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
Submission Time | |
---|---|
Task | F - Many Moves |
User | miaom |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2397 Byte |
Status | CE |
Compile Error
./Main.cpp:8:1: error: ‘ll’ does not name a type ll min(ll x,ll y){ return x<y?x:y; } ^ ./Main.cpp:9:1: error: ‘ll’ does not name a type ll max(ll x,ll y){ return x>y?x:y; } ^ ./Main.cpp:10:1: error: ‘ll’ does not name a type ll abs(ll x){ return x>0?x:-x; } ^ ./Main.cpp: In function ‘void pushdown(long long int, long long int)’: ./Main.cpp:17:48: error: ‘min’ was not declared in this scope seg[op][x<<1]=min(INF,seg[op][x<<1]+tag[op][x]); ^ ./Main.cpp: In function ‘void mdf(long long int, long long int, long long int, long long int, long long int, long long int)’: ./Main.cpp:35:46: error: ‘min’ was not declared in this scope seg[op][x]=min(seg[op][x<<1],seg[op][x<<1|1]); ^ ./Main.cpp: In function ‘long long int qry1(long long int, long long int, long long int, long long int, long long int, long long int)’: ./Main.cpp:46:49: error: ‘min’ was not declared in this scope if (L<=mid) tmp=min(tmp,qry1(op,x...