結果

問題 No.1568 Sushi
ユーザー 👑 hos.lyric
提出日時 2021-06-26 14:35:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,507 bytes
コンパイル時間 1,243 ms
コンパイル使用メモリ 107,332 KB
実行使用メモリ 21,352 KB
最終ジャッジ日時 2024-06-25 10:35:26
合計ジャッジ時間 10,718 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other WA * 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}
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, -2 * L});
seg0 = new SegmentTree<Info, decltype(&mul)>(N + 1, mul, Info{0, -2 * L});
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0