#670272 (C++14) No.1568 Sushi

提出ソース

結果

問題	No.1568 Sushi
ユーザー	👑 hos.lyric
提出日時	2021-06-26 14:37:13
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,503 bytes
コンパイル時間	1,220 ms
コンパイル使用メモリ	107,724 KB
実行使用メモリ	21,376 KB
最終ジャッジ日時	2024-06-25 10:36:15
合計ジャッジ時間	10,278 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


template <class T, class Op> struct SegmentTree {
  const Op op;
  const T idT;

  int n;
  vector<T> ts;
  SegmentTree(int n_, const Op op, const T &idT) : op(op), idT(idT) {
    for (n = 1; n < n_; n <<= 1) {}
    ts.assign(n << 1, idT);
  }
  SegmentTree(const vector<T> &ts_, const Op op, const T &idT)
      : op(op), idT(idT) {
    const int n_ = ts_.size();
    for (n = 1; n < n_; n <<= 1) {}
    ts.assign(n << 1, idT);
    for (int a = 0; a < n_; ++a) ts[n + a] = ts_[a];
    build();
  }
  T &at(int a) {
    return ts[n + a];
  }
  void build() {
    for (int a = n; --a; ) ts[a] = op(ts[a << 1], ts[a << 1 | 1]);
  }
  void set(int a, const T &val) {
    ts[a += n] = val;
    for (; a >>= 1; ) ts[a] = op(ts[a << 1], ts[a << 1 | 1]);
  }
  void mulL(int a, const T &val) {
    set(a, op(val, ts[a + n]));
  }
  void mulR(int a, const T &val) {
    set(a, op(ts[a + n], val));
  }
  T query(int a, int b) const {
    T prodL = idT, prodR = idT;
    for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
      if (a & 1) prodL = op(prodL, ts[a++]);
      if (b & 1) prodR = op(ts[--b], prodR);
    }
    return op(prodL, prodR);
  }

  // min b s.t. pred(prod of [a, b)) (or n + 1 if no such b)
  //   0 <= a <= n
  //   assume pred(prod of [a, b)) is non-decreasing in b
  template <class Pred> int binarySearchR(int a, Pred pred) const {
    if (pred(idT)) return a;
    if (a == n) return n + 1;
    T prod = idT;
    for (a += n; ; a >>= 1) {
      if (a & 1) {
        if (pred(op(prod, ts[a]))) {
          for (; a < n; ) {
            a <<= 1;
            if (!pred(op(prod, ts[a]))) {
              prod = op(prod, ts[a++]);
            }
          }
          return a - n + 1;
        }
        prod = op(prod, ts[a++]);
        if (!(a & (a - 1))) return n + 1;
      }
    }
  }

  // max a s.t. pred(prod of [a, b)) (or -1 if no such a)
  //   0 <= b <= n
  //   assume pred(prod of [a, b)) is non-increasing in a
  template <class Pred> int binarySearchL(int b, Pred pred) const {
    if (pred(idT)) return b;
    if (b == 0) return -1;
    T prod = idT;
    for (b += n; ; b >>= 1) {
      if ((b & 1) || b == 2) {
        if (pred(op(prod, ts[b - 1]))) {
          for (; b <= n; ) {
            b <<= 1;
            if (!pred(op(prod, ts[b - 1]))) {
              prod = op(prod, ts[--b]);
            }
          }
          return b - n - 1;
        }
        prod = op(prod, ts[--b]);
        if (!(b & (b - 1))) return -1;
      }
    }
  }
};


constexpr Int INF = 1001001001001001001LL;

// x -> max{x + c, d}
struct Info {
  Int c, d;
};
Info mul(const Info &t0, const Info &t1) {
  return Info{t0.c + t1.c, max(t0.d + t1.c, t1.d)};
}

Int L;
int N, Q;
vector<Int> A;

Int solveSlow(Int X, Int T) {
// cerr<<"solveSlow "<<X<<" "<<T<<endl;
  const Int xp = -((L - X) % L), xq = X;
  Int p = 0, q = 0;
  const int i0 = upper_bound(A.begin(), A.end(), T) - A.begin();
  for (int i = i0 - 1; i <= N; ++i) {
    const Int a = max(A[i], T), b = A[i + 1];
    const Int len = b - a;
    if (i & 1) {
      if (p - len <= xp) {
        return a + (p - xp) - T;
      }
      p -= len;
      chmax(q -= len, 0LL);
    } else {
      if (xq <= q + len) {
        return a + (xq - q) - T;
      }
      chmin(p += len, 0LL);
      q += len;
    }
  }
  assert(false);
  return 0;
}

SegmentTree<Info, decltype(&mul)> *seg1, *seg0;
void init() {
  seg1 = new SegmentTree<Info, decltype(&mul)>(N + 1, mul, Info{0, -INF});
  seg0 = new SegmentTree<Info, decltype(&mul)>(N + 1, mul, Info{0, -INF});
  for (int i = 0; i <= N; ++i) {
    const Int len = A[i + 1] - A[i];
    seg1->at(i) = Info{((i & 1) ? +1 : -1) * len, 0};
    seg0->at(i) = Info{((i & 1) ? -1 : +1) * len, 0};
  }
  seg1->build();
  seg0->build();
}
Int solve(Int X, Int T) {
// cerr<<"solve "<<X<<" "<<T<<endl;
  const Int xp = -((L - X) % L), xq = X;
// cerr<<"  xp = "<<xp<<", xq = "<<xq<<endl;
  Int p = 0, q = 0;
  const int i0 = upper_bound(A.begin(), A.end(), T) - A.begin();
  {
    const int i = i0 - 1;
    const Int a = max(A[i], T), b = A[i + 1];
    const Int len = b - a;
    if (i & 1) {
      if (p - len <= xp) {
        return a + (p - xp) - T;
      }
      p -= len;
      chmax(q -= len, 0LL);
    } else {
      if (xq <= q + len) {
        return a + (xq - q) - T;
      }
      chmin(p += len, 0LL);
      q += len;
    }
  }
// cerr<<"  ["<<p<<", "<<q<<"]"<<endl;
  Int ans = INF;
  {
    const int i = seg1->binarySearchR(i0, [&](const Info &t) {
      return (-max(-p + t.c, t.d) <= xp);
    }) - 1;
// cerr<<"  seg1 i = "<<i<<endl;
    if (i <= N) {
      const Info t = seg1->query(i0, i);
      const Int pp = -max(-p + t.c, t.d);
      chmin(ans, A[i] + (pp - xp) - T);
    }
  }
  {
    const int i = seg0->binarySearchR(i0, [&](const Info &t) {
      return (xq <= max(q + t.c, t.d));
    }) - 1;
// cerr<<"  seg0 i = "<<i<<endl;
    if (i <= N) {
      const Info t = seg0->query(i0, i);
      const Int qq = max(q + t.c, t.d);
      chmin(ans, A[i] + (xq - qq) - T);
    }
  }
  return ans;
}

int main() {
  for (; ~scanf("%lld%d%d", &L, &N, &Q); ) {
    A.resize(N + 2);
    A[0] = 0;
    for (int i = 1; i <= N; ++i) {
      scanf("%lld", &A[i]);
    }
    A[N + 1] = A[N] + 2 * L;
    
    init();
    
    Int ans = 0;
    for (; Q--; ) {
      Int b, c;
      scanf("%lld%lld", &b, &c);
      const Int x = (b + ans) % L;
      const Int t = (c + ans) % 1'000'000'000'000'000LL;
      ans = solve(x, t);
      printf("%lld\n", ans);
#ifdef LOCAL
const Int slw=solveSlow(x,t);
if(slw!=ans){cerr<<"slw = "<<slw<<endl;assert(false);}
#endif
    }
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード