Submission #1871604
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(){
freopen("light.in","r",stdin); freopen("light.out","w",stdout);
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 |
2478 Byte |
Status |
RE |
Exec Time |
117 ms |
Memory |
65664 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:64:31: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("light.in","r",stdin); freopen("light.out","w",stdout);
^
./Main.cpp:64:64: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("light.in","r",stdin); freopen("light.out","w",stdout);
^
./Main.cpp:65: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:71:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&a[i]);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2, example3 |
All |
example0, example1, example2, example3, flower0, flower1, flower2, flower3, flower4, flower5, flower6, flower7, flower8, flower9, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, smallrand0, smallrand1, smallrand2, smallrand3, smallrand4, smallrand5, smallrand6, smallrand7, smallrand8, smallrand9 |
Case Name |
Status |
Exec Time |
Memory |
example0 |
RE |
116 ms |
65664 KB |
example1 |
RE |
116 ms |
65664 KB |
example2 |
RE |
116 ms |
65664 KB |
example3 |
RE |
116 ms |
65664 KB |
flower0 |
RE |
115 ms |
65664 KB |
flower1 |
RE |
116 ms |
65664 KB |
flower2 |
RE |
116 ms |
65664 KB |
flower3 |
RE |
116 ms |
65664 KB |
flower4 |
RE |
116 ms |
65664 KB |
flower5 |
RE |
116 ms |
65664 KB |
flower6 |
RE |
117 ms |
65664 KB |
flower7 |
RE |
116 ms |
65664 KB |
flower8 |
RE |
115 ms |
65664 KB |
flower9 |
RE |
116 ms |
65664 KB |
maxrand0 |
RE |
117 ms |
65664 KB |
maxrand1 |
RE |
114 ms |
65664 KB |
maxrand2 |
RE |
115 ms |
65664 KB |
maxrand3 |
RE |
116 ms |
65664 KB |
maxrand4 |
RE |
116 ms |
65664 KB |
maxrand5 |
RE |
116 ms |
65664 KB |
maxrand6 |
RE |
117 ms |
65664 KB |
maxrand7 |
RE |
117 ms |
65664 KB |
maxrand8 |
RE |
117 ms |
65664 KB |
maxrand9 |
RE |
116 ms |
65664 KB |
smallrand0 |
RE |
117 ms |
65664 KB |
smallrand1 |
RE |
116 ms |
65664 KB |
smallrand2 |
RE |
116 ms |
65664 KB |
smallrand3 |
RE |
116 ms |
65664 KB |
smallrand4 |
RE |
117 ms |
65664 KB |
smallrand5 |
RE |
117 ms |
65664 KB |
smallrand6 |
RE |
115 ms |
65664 KB |
smallrand7 |
RE |
116 ms |
65664 KB |
smallrand8 |
RE |
116 ms |
65664 KB |
smallrand9 |
RE |
117 ms |
65664 KB |