結果

問題 No.1568 Sushi
ユーザー 👑 hos.lyrichos.lyric
提出日時 2021-06-26 14:53:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 414 ms / 2,000 ms
コード長 6,892 bytes
コンパイル時間 1,229 ms
コンパイル使用メモリ 107,072 KB
実行使用メモリ 37,664 KB
最終ジャッジ日時 2024-06-25 10:38:58
合計ジャッジ時間 13,685 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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}
  
  x -> max{x + cm, dm}
  max{max{x + cm, dm}, max{max{x + c, d} + cm', dm'}
  = max{x + cm, dm, x + c + cm', d + cm', dm'}
*/
struct Info {
  Int c, d;
  Int cm, dm;
};
Info mul(const Info &t0, const Info &t1) {
  return Info{
      t0.c + t1.c, max(t0.d + t1.c, t1.d),
      max(t0.cm, t0.c + t1.cm), max({t0.dm, t0.d + t1.cm, t1.dm}),
  };
}

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;
// cerr<<"  solveSlow "<<i<<" ["<<p<<", "<<q<<"]"<<" ["<<a<<", "<<b<<"] "<<len<<endl;
    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, 0, -INF});
  seg0 = new SegmentTree<Info, decltype(&mul)>(N + 1, mul, Info{0, -INF, 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, ((i & 1) ? +1 : 0) * len, 0};
    seg0->at(i) = Info{((i & 1) ? -1 : +1) * len, 0, ((i & 1) ? 0 : +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.cm, t.dm) <= 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.cm, t.dm));
    }) - 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;
}
0