結果
問題 | No.1568 Sushi |
ユーザー |
![]() |
提出日時 | 2021-06-26 13:56:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,221 bytes |
コンパイル時間 | 1,737 ms |
コンパイル使用メモリ | 177,756 KB |
実行使用メモリ | 35,400 KB |
最終ジャッジ日時 | 2024-06-25 10:30:29 |
合計ジャッジ時間 | 7,951 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | WA * 5 TLE * 1 -- * 19 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long INF = 10000000000000000;struct monoid{bool id;long long mn, mx, inc, dec;monoid(){id = true;}monoid(long long a){id = false;mn = a;mx = a;inc = 0;dec = 0;}monoid(long long L, long long R){id = false;mn = min(L, R);mx = max(L, R);inc = max(R - L, (long long) 0);dec = min(R - L, (long long) 0);}};monoid f(monoid L, monoid R){if (L.id){return R;}if (R.id){return L;}monoid ans;ans.id = false;ans.mn = min(L.mn, R.mn);ans.mx = max(L.mx, R.mx);ans.inc = max({L.inc, R.inc, R.mx - L.mn});ans.dec = min({L.dec, R.dec, R.mn - L.mx});return ans;}struct segment_tree{int N;vector<long long> A;vector<long long> S;vector<monoid> ST;segment_tree(vector<long long> A): A(A){A.push_back(INF);int N2 = A.size();S = vector<long long>(N2 + 1);long long P = 0;S[0] = 0;for (int i = 0; i < N2; i++){if (i % 2 == 0){S[i + 1] = S[i] + (A[i] - P);} else {S[i + 1] = S[i] - (A[i] - P);}P = A[i];}N = 1;while (N < N2){N *= 2;}ST = vector<monoid>(N * 2 - 1);for (int i = 0; i < N2; i++){ST[N - 1 + i] = monoid(S[i], S[i + 1]);}for (int i = N - 2; i >= 0; i--){ST[i] = f(ST[i * 2 + 1], ST[i * 2 + 2]);}}monoid range_fold(int L, int R, int i, int l, int r){if (r <= L || R <= l){return monoid();} else if (L <= l && r <= R){return ST[i];} else {int m = (l + r) / 2;return f(range_fold(L, R, i * 2 + 1, l, m), range_fold(L, R, i * 2 + 2, m, r));}}monoid query(long long tL, long long tR){int L = lower_bound(A.begin(), A.end(), tL) - A.begin();int R = lower_bound(A.begin(), A.end(), tR) - A.begin() - 1;if (R == L - 1){if (L % 2 == 0){return monoid(S[L + 1] - (A[L] - tL), S[L + 1] - (A[L] - tR));} else {return monoid(S[L + 1] + (A[L] - tL), S[L + 1] + (A[L] - tR));}}monoid l;if (L % 2 == 0){l = monoid(S[L + 1] - (A[L] - tL), S[L + 1]);} else {l = monoid(S[L + 1] + (A[L] - tL), S[L + 1]);}monoid m = range_fold(L, R, 0, 0, N);monoid r;if (R % 2 == 0){r = monoid(S[R + 1], S[R + 1] - (tR - A[R]));} else {r = monoid(S[R + 1], S[R + 1] + (tR - A[R]));}monoid ans = f(f(l, m), r);return ans;}};int main(){long long L;int N, Q;cin >> L >> N >> Q;vector<long long> A(N);for (int i = 0; i < N; i++){cin >> A[i];}segment_tree ST(A);long long D = 0;for (int i = 0; i < Q; i++){long long B, C;cin >> B >> C;long long x, t;if (i == 0){x = B;t = C;} else {x = (B + D) % L;t = (C + D) % 1000000000000000;}long long tv = INF, fv = t - 1;while (tv - fv > 1){long long mid = (tv + fv) / 2;monoid M = ST.query(t, mid);assert(!M.id);if (M.inc >= x || M.dec <= -L + x){tv = mid;} else {fv = mid;}}D = tv - t;cout << D << "\n";}}