保存されている過去のバージョンの一覧

2021年05月20日22時27分55秒

AtCoder Regular Contest 119 E問題 - Pancakes

Source

AtCoder Regular Contest 119
問題文

問題概要

省略

解法

省略

cLay（version 20210405-1）のコード

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月19日21時26分07秒
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)

ログイン：