Submission #1693269
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]=z-l;
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=0x3f3f3f3f;
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
Submission Time
2017-10-19 15:47:39+0900
Task
F - Many Moves
User
SD_le
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1820 Byte
Status
WA
Exec Time
166 ms
Memory
20608 KB
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
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
AC
5 ms
12800 KB
example1
AC
6 ms
12800 KB
example2
AC
6 ms
12928 KB
example3
AC
6 ms
12800 KB
flower0
WA
152 ms
20608 KB
flower1
WA
153 ms
20608 KB
flower2
WA
152 ms
20608 KB
flower3
WA
155 ms
20608 KB
flower4
WA
159 ms
20608 KB
flower5
WA
152 ms
20608 KB
flower6
WA
154 ms
20608 KB
flower7
WA
155 ms
20608 KB
flower8
WA
152 ms
20608 KB
flower9
WA
152 ms
20608 KB
maxrand0
WA
162 ms
20608 KB
maxrand1
WA
159 ms
20608 KB
maxrand2
WA
161 ms
20608 KB
maxrand3
WA
164 ms
20608 KB
maxrand4
WA
157 ms
20608 KB
maxrand5
WA
160 ms
20608 KB
maxrand6
WA
166 ms
20608 KB
maxrand7
WA
161 ms
20608 KB
maxrand8
WA
163 ms
20608 KB
maxrand9
WA
165 ms
20608 KB
smallrand0
AC
6 ms
12800 KB
smallrand1
AC
6 ms
12928 KB
smallrand2
AC
6 ms
12928 KB
smallrand3
AC
6 ms
12800 KB
smallrand4
AC
6 ms
12928 KB
smallrand5
AC
6 ms
12928 KB
smallrand6
AC
6 ms
12800 KB
smallrand7
AC
6 ms
12928 KB
smallrand8
AC
6 ms
12928 KB
smallrand9
AC
6 ms
12800 KB