Submission #2231797
Source Code Expand
#include <bits/stdc++.h>
const int maxn=2e5+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
Submission Time
2018-03-19 18:42:36+0900
Task
F - Many Moves
User
mxzf0213
Language
C++14 (GCC 5.4.1)
Score
900
Code Size
2659 Byte
Status
AC
Exec Time
268 ms
Memory
18688 KB
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
Set Name
Sample
All
Score / Max Score
0 / 0
900 / 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
1 ms
256 KB
example1
AC
1 ms
256 KB
example2
AC
1 ms
256 KB
example3
AC
1 ms
256 KB
flower0
AC
253 ms
18688 KB
flower1
AC
248 ms
18688 KB
flower2
AC
257 ms
18688 KB
flower3
AC
249 ms
18688 KB
flower4
AC
240 ms
18688 KB
flower5
AC
246 ms
18688 KB
flower6
AC
238 ms
18688 KB
flower7
AC
246 ms
18688 KB
flower8
AC
244 ms
18688 KB
flower9
AC
263 ms
18688 KB
maxrand0
AC
267 ms
18688 KB
maxrand1
AC
266 ms
18688 KB
maxrand2
AC
258 ms
18688 KB
maxrand3
AC
261 ms
18688 KB
maxrand4
AC
268 ms
18688 KB
maxrand5
AC
248 ms
18688 KB
maxrand6
AC
247 ms
18688 KB
maxrand7
AC
248 ms
18688 KB
maxrand8
AC
251 ms
18688 KB
maxrand9
AC
251 ms
18688 KB
smallrand0
AC
1 ms
256 KB
smallrand1
AC
1 ms
256 KB
smallrand2
AC
1 ms
256 KB
smallrand3
AC
1 ms
256 KB
smallrand4
AC
1 ms
256 KB
smallrand5
AC
1 ms
256 KB
smallrand6
AC
1 ms
256 KB
smallrand7
AC
1 ms
256 KB
smallrand8
AC
1 ms
256 KB
smallrand9
AC
1 ms
256 KB