#1191230 (D) No.3750 Mischievous Resident (Easy)

• 問題: No.3750 Mischievous Resident (Easy)
• ユーザー: hos.lyric
• 提出日時: 2026-10-02 23:25:58
• 言語: D (dmd 2.113.0)
• 結果: AC
• 実行時間: 154 ms / 2,000 ms
• コード長: 5,790 bytes
• コンパイル時間: 3,715 ms
• コンパイル使用メモリ: 141,428 KB
• 実行使用メモリ: 20,356 KB
• 最終ジャッジ日時: 2026-10-02 23:26:28
• 合計ジャッジ時間: 8,978 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 35

ソースコード

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)); }


// floor(a / b)
Int divFloor(Int)(Int a, Int b) {
  return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}

// ceil(a / b)
Int divCeil(Int)(Int a, Int b) {
  return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}


long calc(long a, long b) {
  if (b == 0) {
    assert(a == 0);
    return 0;
  }
  // assert(a >= b);
  assert(b > 0);
  /*
  long cost;
  for (; a > b; ) {
    ++cost;
    a = (a + 1) / 2;
  }
  return cost;
  */
  return (a <= b) ? 0 : (bsr(((a+b-1)/b) - 1) + 1);
}
/*
long calc2(long n, long a, long b) {
  assert(0 <= a); assert(a < b); assert(b <= n);
  long ret = long.max;
  long l = 0, r = n;
  if (a <= l) chmin(ret, calc(r - a, b - a));
  if (r <= b) chmin(ret, calc(b - l, b - a));
  long cost;
  for (; l < a && b < r; ) {
    const d = (r - l) / 2;
    ++cost;
    if (a <= l + d) chmin(ret, cost + calc(r - a, b - a));
    if (r - d <= b) chmin(ret, cost + calc(b - l, b - a));
    if (a <= l + d) {
      r -= d;
    } else if (r - d <= b) {
      l += d;
    } else assert(false);
  }
  return ret;
}
*/
long calc2(long n, long a, long b) {
  assert(0 <= a); assert(a < b); assert(b <= n);
  if (a == 0 || b == n) return calc(n, b - a);
  long ret = long.max;
  // [l, l + 2^e d], [l + d, l + d + 2^e d], ..., [r, r + 2^e d] \subseteq [0, n]
  const d = b - a;
  long l = a, r = a;
  for (long e = 0; l <= r; ++e) {
    l -= (d << e);
// writefln("[calc2] n=%s, a=%s, b=%s; e=%s, l=%s, r=%s",n,a,b,e,l,r);
    bool any;
    if (l <= 0) {
      any = true;
      const ll = min(l + divFloor(0 - l, d) * d, r);
      chmin(ret, e + 1 + calc(n, ll + (d << (e+1))));
      l += divCeil(0 - l, d) * d;
    }
    if (n <= r + (d << (e+1))) {
      any = true;
      const rr = max(r - divFloor(r + (d << (e+1)) - n, d) * d, l);
      chmin(ret, e + 1 + calc(n, n - rr));
      r -= divCeil(r + (d << (e+1)) - n, d) * d;
    }
// writefln("[calc2] n=%s, a=%s, b=%s; e=%s, l=%s, r=%s",n,a,b,e,l,r);
    if (any) break;
  }
  return ret;
}

void exper() {
  foreach (N; 1 .. 100 + 1) {
    // (0, N) -> (a, b)
    int enc(int a, int b) {
      return a * (N+1) + b;
    }
    const U = (N+1) * (N+1);
    auto d = new int[][](U, U);
    foreach (u; 0 .. U) d[u][] = U;
    foreach (u; 0 .. U) d[u][u] = 0;
    foreach (a; 0 .. N + 1) foreach (b; 0 .. N + 1) {
      foreach (c; 0 .. N + 1) {
        if (abs(a - c) <= abs(b - c)) chmin(d[enc(a, b)][enc(c, b)], 1);
        if (abs(a - c) >= abs(b - c)) chmin(d[enc(a, b)][enc(a, c)], 1);
      }
    }
    foreach (w; 0 .. U) foreach (u; 0 .. U) foreach (v; 0 .. U) chmin(d[u][v], d[u][w] + d[w][v]);
    foreach (a; 0 .. N + 1) foreach (b; 0 .. N + 1) {
      const brt = d[enc(0, N)][enc(a, b)];
      // writeln(N, " ", a, " ", b, ": ", brt);
      if (a < b) {
        // writeln(N, " ", a, " ", b, ": ", brt);
        assert(brt < U);
        // const grd = min(calc(N, N - a) + calc(N - a, b - a), calc(N, b) + calc(b, b - a));
        const grd = calc2(N, a, b);
        assert(brt == grd, format("%s %s %s: %s %s", N, a, b, brt, grd));
      }
    }
    stderr.writefln("PASSED N = %s", N);
    stderr.flush;
  }
}

void main() {
  // exper; return;
  
  try {
    for (; ; ) {
      const numCases = readInt;
      foreach (caseId; 0 .. numCases) {
        const N = readLong;
        const M = readInt;
        alias Entry = Tuple!(long, "s", long, "t");
        auto E = new Entry[M];
        foreach (i; 0 .. M) E[i].s = readLong;
        foreach (i; 0 .. M) E[i].t = readLong;
        E.sort;
        debug writeln(E);
        
        bool ok = true;
        foreach (i; 1 .. M) {
          if (E[i - 1].s < E[i].s) {
            ok = ok && (E[i - 1].t < E[i].t);
          } else {
            ok = ok && (E[i - 1].s == E[i - 1].t || E[i].s == E[i].t || E[i - 1].t < E[i].t);
          }
        }
        if (ok) {
          long ans;
          for (int l = 0, m, r; l < M; l = r) {
            for (m = l; m < M && E[m].s <= E[m].t; ++m) {}
            for (r = m; r < M && E[r].s >= E[r].t; ++r) {}
            if (m - l == 0 || r - m == 0) {
              if (l < m && E[m - 1].s != E[m - 1].t) ans += 1;
              if (m < r && E[m].s != E[m].t) ans += 1;
            } else {
              ans += calc2(E[m].s - E[m - 1].s, E[m - 1].t - E[m - 1].s, E[m].t - E[m - 1].s);
            }
            foreach (i; l .. m - 1) ans += calc(E[i + 1].t - E[i].s, E[i + 1].t - E[i].t);
            foreach (i; m + 1 .. r) ans += calc(E[i].s - E[i - 1].t, E[i].t - E[i - 1].t);
          }
          writeln("Yes");
        } else {
          writeln("No");
        }
      }
    }
  } catch (EOFException e) {
  }
}