結果

問題 No.704 ゴミ拾い Medium
コンテスト
ユーザー hos.lyric
提出日時 2019-01-23 15:47:59
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 338 ms / 1,500 ms
コード長 3,316 bytes
コンパイル時間 1,203 ms
コンパイル使用メモリ 126,224 KB
実行使用メモリ 33,452 KB
最終ジャッジ日時 2024-06-13 03:32:39
合計ジャッジ時間 10,342 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


enum INF = 10L^^18;

class SegmentTree {
  int n;
  long[] mn;
  this(int n_) {
    for (n = 1; n < n_; n <<= 1) {}
    mn = new long[n << 1];
    mn[] = INF;
  }
  void update(int a, long val) {
    chmin(mn[a += n], val);
    for (a >>= 1; a; a >>= 1) {
      mn[a] = min(mn[a << 1], mn[a << 1 | 1]);
    }
  }
  long rangeMin(int a, int b) {
    long ret = INF;
    for (a += n, b += n; a <= b; a >>= 1, b >>= 1) {
      if ( a & 1) chmin(ret, mn[a++]);
      if (~b & 1) chmin(ret, mn[b--]);
    }
    return ret;
  }
}

int N;
long[] A, X, Y;

void main() {
  try {
    for (; ; ) {
      N = readInt();
      A = new long[N];
      foreach (i; 0 .. N) {
        A[i] = readLong();
      }
      X = new long[N];
      foreach (i; 0 .. N) {
        X[i] = readLong();
      }
      Y = new long[N];
      foreach (i; 0 .. N) {
        Y[i] = readLong();
      }
      
      debug {
        auto dp = new long[N];
        foreach (i; 0 .. N) {
          dp[i] = abs(X[0] - A[i]) + abs(Y[0] - 0);
          foreach (j; 1 .. i + 1) {
            chmin(dp[i], dp[j - 1] + abs(X[j] - A[i]) + abs(Y[j] - 0));
          }
        }
        writeln(dp);
      }
      
      /*
        dp[i] = min{ dp[j - 1] + |X[j] - A[i]| + |Y[j] - 0| | 0 <= j <= i }
              = min{
                  min{ dp[j - 1] - X[j] + |Y[j]| | X[j] <  A[i] } + A[i],
                  min{ dp[j - 1] + X[j] + |Y[j]| | X[j] >= A[i] } - A[i]
                }
      */
      const xs = X.dup.sort.uniq.array;
      const xsLen = cast(int)(xs.length);
      auto segL = new SegmentTree(xsLen);
      auto segR = new SegmentTree(xsLen);
      long ans;
      foreach (i; -1 .. N) {
        long z;
        if (i == -1) {
          z = 0;
        } else {
          z = min(
            segL.rangeMin(0, xs.lowerBound(A[i]) - 1) + A[i],
            segR.rangeMin(xs.lowerBound(A[i]), xsLen - 1) - A[i]
          );
        }
        debug {
          writeln(i, " ", z);
        }
        if (i == N - 1) {
          ans = z;
        } else {
          const pos = xs.lowerBound(X[i + 1]);
          segL.update(pos, z - X[i + 1] + abs(Y[i + 1]));
          segR.update(pos, z + X[i + 1] + abs(Y[i + 1]));
        }
      }
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}
0