Submission #2231796
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:25+0900
Task
C - Sentou
User
mxzf0213
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2659 Byte
Status
RE
Exec Time
107 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
0 / 300
Status
Set Name
Test Cases
Sample
example0, example1, example2, example3, example4
All
example0, example1, example2, example3, example4, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2, rand3, rand4
Case Name
Status
Exec Time
Memory
example0
RE
99 ms
256 KB
example1
RE
100 ms
256 KB
example2
RE
99 ms
256 KB
example3
RE
99 ms
256 KB
example4
RE
100 ms
256 KB
maxrand0
RE
107 ms
18688 KB
maxrand1
RE
106 ms
18688 KB
maxrand2
RE
107 ms
18688 KB
rand0
RE
99 ms
256 KB
rand1
RE
100 ms
256 KB
rand2
RE
100 ms
256 KB
rand3
RE
100 ms
256 KB
rand4
RE
100 ms
256 KB