AtCoder Regular Contest 119
問題文
省略
省略
C++に変換後のコードはこちら
int N; ll A[3d5];
segtree_Point_Minval<ll> t1, t2;
ll x[3d5], y[3d5], p[3d5];
int rx[3d5];
{
ll res = 0;
rd(N,A(N));
rep(i,N-1){
x[i] = A[i];
y[i] = A[i+1];
p[i] = abs(x[i] - y[i]);
}
t1.walloc(N); t2.walloc(N);
t1.setN(N); t2.setN(N);
rep(i,N) t1[i] = t2[i] = ll_inf;
t1.build(); t2.build();
sortA(N-1, y, x, p);
coordcomp(N-1, x, rx);
rep(i,N-1){
if(0 < rx[i]) res <?= t1.getMinVal(0, rx[i]) + x[i] + y[i] - p[i];
if(rx[i] < N) res <?= t2.getMinVal(rx[i], N) - x[i] + y[i] - p[i];
t1.change(rx[i], -x[i] - y[i] - p[i]);
t2.change(rx[i], x[i] - y[i] - p[i]);
}
rep(i,N-1) res <?= abs(A[i] - A[N-1]) - abs(A[i] - A[i+1]);
rep(i,N-1) res <?= abs(A[0] - A[i+1]) - abs(A[i] - A[i+1]);
rep(i,1,N) res += abs(A[i] - A[i-1]);
wt(res);
}
Current time: 2024年04月26日23時20分36秒
Last modified: 2021年05月20日22時27分55秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Regular_Contest ARC119 ARC_E
トップページに戻る
Logged in as: unknown user (not login)