結果
| 問題 | No.1568 Sushi |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2021-06-26 14:37:13 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | WA * 25 |
ソースコード
#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 btemplate <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 atemplate <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 LOCALconst Int slw=solveSlow(x,t);if(slw!=ans){cerr<<"slw = "<<slw<<endl;assert(false);}#endif}}return 0;}