Submission #2231789
Source Code Expand
#include <bits/stdc++.h>
const int maxn=1e5+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:40:52+0900
Task
F - Many Moves
User
mxzf0213
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2659 Byte
Status
RE
Exec Time
114 ms
Memory
11776 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
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
1 ms
256 KB
example1
AC
1 ms
256 KB
example2
AC
1 ms
256 KB
example3
AC
1 ms
256 KB
flower0
RE
113 ms
11776 KB
flower1
RE
113 ms
11776 KB
flower2
RE
114 ms
11776 KB
flower3
RE
110 ms
11776 KB
flower4
RE
111 ms
11776 KB
flower5
RE
109 ms
11776 KB
flower6
RE
110 ms
11776 KB
flower7
RE
108 ms
11776 KB
flower8
RE
112 ms
11776 KB
flower9
RE
109 ms
11776 KB
maxrand0
RE
111 ms
11776 KB
maxrand1
RE
111 ms
11776 KB
maxrand2
RE
111 ms
11776 KB
maxrand3
RE
110 ms
11776 KB
maxrand4
RE
110 ms
11776 KB
maxrand5
RE
112 ms
11776 KB
maxrand6
RE
109 ms
11776 KB
maxrand7
RE
109 ms
11776 KB
maxrand8
RE
113 ms
11776 KB
maxrand9
RE
111 ms
11776 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