Submission #1694855
Source Code Expand
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
// _oo0oo_ //
// o8888888o //
// 88" . "88 ------ hzt1 //
// (| -_- |) //
// 0\ = /0 //
// ___/`---'\___ //
// .' \| |// '. //
// / \||| : |||// \ //
// / _||||| -:- |||||- \ //
// | | \ - /// | | //
// | \_| ''\---/'' |_/ | //
// \ .-\__ '-' ___/-. / //
// ___'. .' /--.--\ `. .'___ //
// ."" '< `.___\_<|>_/___.' >' "". //
// | | : `- \`.;`\ _ /`;.`/ - ` : | | //
// \ \ `_. \_ __\ /__ _/ .-` / / //
// =====`-.____`.___ \_____/___.-`___.-'===== //
// `=---=' //
// //
// //
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //
// //
// God-He Bless All. //
// This Code Will Never Explode. //
// //
// //
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
const int Size=1<<16;
char buffer[Size],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,1,Size,stdin);
tail=(head=buffer)+l;
}
if(head==tail) return -1;
return *head++;
}
inline int read() {
int x=0,f=1;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
return x*f;
}
typedef long long ll;
const int maxn=200010;
const ll inf=1ll<<60;
int n,q,a,b,x[maxn];
ll minv[maxn<<2][2];
void update(int o,int l,int r,int p,ll v) {
if(l==r) {
minv[o][0]=min(minv[o][0],v-l);
minv[o][1]=min(minv[o][1],v+l);
}
else {
int mid=l+r>>1,lc=o<<1,rc=lc|1;
if(p<=mid) update(lc,l,mid,p,v);
else update(rc,mid+1,r,p,v);
minv[o][0]=min(minv[lc][0],minv[rc][0]);
minv[o][1]=min(minv[lc][1],minv[rc][1]);
}
}
ll query(int o,int l,int r,int ql,int qr,int tp) {
if(ql<=l&&r<=qr) return minv[o][tp];
int mid=l+r>>1,lc=o<<1,rc=lc|1;ll res=inf;
if(ql<=mid) res=min(res,query(lc,l,mid,ql,qr,tp));
if(qr>mid) res=min(res,query(rc,mid+1,r,ql,qr,tp));
return res;
}
ll add;
int main() {
n=read();q=read();a=read();b=read();
rep(i,1,n*4) minv[i][0]=minv[i][1]=inf;
x[0]=a;update(1,1,n,b,0);
rep(i,1,q) {
x[i]=read();add+=abs(x[i]-x[i-1]);
ll v1=query(1,1,n,1,x[i],0)+x[i]-abs(x[i]-x[i-1]),v2=query(1,1,n,x[i],n,1)-x[i]-abs(x[i]-x[i-1]);
update(1,1,n,x[i-1],min(v1,v2));
}
ll ans=inf;
rep(i,1,n) ans=min(ans,add+query(1,1,n,1,i,0)+i);
printf("%lld\n",ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Many Moves |
User |
wzj52501 |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
3714 Byte |
Status |
AC |
Exec Time |
143 ms |
Memory |
13440 KB |
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 |
128 KB |
example1 |
AC |
1 ms |
128 KB |
example2 |
AC |
1 ms |
128 KB |
example3 |
AC |
1 ms |
128 KB |
flower0 |
AC |
126 ms |
13440 KB |
flower1 |
AC |
128 ms |
13440 KB |
flower2 |
AC |
133 ms |
13440 KB |
flower3 |
AC |
132 ms |
13440 KB |
flower4 |
AC |
134 ms |
13440 KB |
flower5 |
AC |
131 ms |
13440 KB |
flower6 |
AC |
131 ms |
13440 KB |
flower7 |
AC |
130 ms |
13440 KB |
flower8 |
AC |
128 ms |
13440 KB |
flower9 |
AC |
130 ms |
13440 KB |
maxrand0 |
AC |
132 ms |
13440 KB |
maxrand1 |
AC |
138 ms |
13440 KB |
maxrand2 |
AC |
142 ms |
13440 KB |
maxrand3 |
AC |
142 ms |
13440 KB |
maxrand4 |
AC |
140 ms |
13440 KB |
maxrand5 |
AC |
143 ms |
13440 KB |
maxrand6 |
AC |
139 ms |
13440 KB |
maxrand7 |
AC |
143 ms |
13440 KB |
maxrand8 |
AC |
143 ms |
13440 KB |
maxrand9 |
AC |
138 ms |
13440 KB |
smallrand0 |
AC |
1 ms |
128 KB |
smallrand1 |
AC |
1 ms |
128 KB |
smallrand2 |
AC |
1 ms |
128 KB |
smallrand3 |
AC |
1 ms |
128 KB |
smallrand4 |
AC |
1 ms |
128 KB |
smallrand5 |
AC |
1 ms |
128 KB |
smallrand6 |
AC |
1 ms |
128 KB |
smallrand7 |
AC |
1 ms |
128 KB |
smallrand8 |
AC |
1 ms |
128 KB |
smallrand9 |
AC |
1 ms |
128 KB |