Submission #65067981

---

Source Code Expand

import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, 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; }

string COLOR(string s = "") { return "\x1b[" ~ s ~ "m"; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


enum INF = 10L^^18;

int[] brute(int N, long D, long[] T, long[] X) {
  bool check(int[] us) {
    const s = us[0];
    long t = 0 + X[s];
    chmax(t, T[s]);
    if (t > T[s] + D) return false;
    int u = s;
    foreach (v; us[1 .. N]) {
      t += X[u] + X[v];
      chmax(t, T[v]);
      if (t > T[v] + D) return false;
      u = v;
    }
    return true;
  }
  auto us = iota(N).array;
  do {
    if (check(us)) return us;
  } while (us.nextPermutation);
  return null;
}

bool solve0(int N, long D, long[] T, long[] X) {
  bool check(int s) {
    long t = 0 + X[s];
    chmax(t, T[s]);
    if (t > T[s] + D) return false;
    int u = s;
    foreach (v; 0 .. N) if (s != v) {
      t += X[u] + X[v];
      chmax(t, T[v]);
      if (t > T[v] + D) return false;
      u = v;
    }
    return true;
  }
  foreach (s; 0 .. N) if (check(s)) return true;
  return false;
}

bool solve1(int N, long D, long[] T, long[] X) {
  bool check(int s) {
    long t = T[s] + D;
    if (t - X[s] < 0) return false;
    int u = s;
    foreach_reverse (v; 0 .. N) if (s != v) {
      t -= X[u] + X[v];
      chmin(t, T[v] + D);
      if (t < T[v]) return false;
      if (t - X[v] < 0) return false;
      u = v;
    }
    return true;
  }
  foreach (s; 0 .. N) if (check(s)) return true;
  return false;
}

bool solve2(int N, long D, long[] T, long[] X) {
  auto dp = new long[N + 1];
  dp[] = INF;
  dp[0] = 0;
  foreach (i; 0 .. N) if (dp[i] < INF) {
    {
      long t = dp[i] + X[i];
      chmax(t, T[i]);
      if (t <= T[i] + D) {
        t += X[i];
        chmin(dp[i + 1], t);
      }
    }
    long minT = +INF;
    long maxT = -INF;
    long sumX;
    long[2] xs = [-INF, -INF];
    foreach (j; i .. N) {
      chmin(minT, T[j]);
      chmax(maxT, T[j]);
      sumX += X[j];
      {
        long x = X[j];
        foreach (k; 0 .. 2) if (xs[k] < x) swap(xs[k], x);
      }
      if (i < j) {
        foreach (k; 0 .. 2) {
          long t = dp[i] + xs[k];
          chmax(t, maxT);
          t += (2 * sumX - xs[0] - xs[1]);
          if (t <= minT + D) {
            t += xs[k ^ 1];
            debug writefln("%s -> %s: %s %s %s %s; %s -> %s", i, j + 1, minT, maxT, sumX, xs, dp[i], t);
            chmin(dp[j + 1], t);
          }
        }
      }
    }
  }
  return (dp[N] < INF);
}

void main() {
  try {
    for (; ; ) {
      const numCases = readInt;
      foreach (caseId; 0 .. numCases) {
        const N = readInt;
        const D = readLong;
        auto T = new long[N];
        auto X = new long[N];
        foreach (u; 0 .. N) {
          T[u] = readLong;
          X[u] = readLong;
        }
        
        const ans = solve0(N, D, T, X) || solve1(N, D, T, X) || solve2(N, D, T, X);
        writeln(ans ? "Yes" : "No");
        debug {
          const brt = brute(N, D, T, X);
          assert(brt ? ans : !ans, format("%s %s %s %s: %s %s", N, D, T, X, brt, ans));
        }
      }
    }
  } catch (EOFException e) {
  }
}

Submission Info

Judge Result