結果
問題 | No.1568 Sushi |
ユーザー |
👑 ![]() |
提出日時 | 2021-06-26 14:32:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,651 bytes |
コンパイル時間 | 1,229 ms |
コンパイル使用メモリ | 98,144 KB |
最終ジャッジ日時 | 2025-01-22 13:24:12 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 13 WA * 12 |
ソースコード
#include <iostream>#include <vector>#include <atcoder/segtree>using namespace std;using ll = long long;using ull = unsigned long long;#define rep(i,n) for(int i=0; i<(n); i++)struct RQS {ll minx, maxx, mindx, maxdx, dx;};RQS RQop(RQS l, RQS r) {RQS res;res.minx = min(l.minx, l.dx + r.minx);res.maxx = max(l.maxx, l.dx + r.maxx);res.mindx = min(min(l.mindx,r.mindx), (r.minx + l.dx) - l.maxx);res.maxdx = max(max(l.maxdx,r.maxdx), (r.maxx + l.dx) - l.minx);res.dx = l.dx + r.dx;return res;}RQS RQe() { return { 0,0,0,0,0 }; }using RQ = atcoder::segtree<RQS, RQop, RQe>;RQS RQ_moveCCW(ll d){ return RQS{ -d,0,-d,0,-d }; }RQS RQ_moveCW(ll d){ return RQS{ 0,d,0,d,d }; }ll L,N,Q;vector<ll> A;vector<ll> dA;ll queryKey_D = 0;int ubound_A(ll t){int l = 0, r = N+1;while(r-l > 1){int m = (l+r) / 2;if(A[m-1] <= t) l = m; else r = m;}return l;}int main(){cin >> L >> N >> Q;A.resize(N+1,0);rep(i,N) cin >> A[i+1];RQ G(N);for(int i=0; i<N; i++){if(i%2 == 0) G.set(i,RQ_moveCCW(A[i+1]-A[i]));else G.set(i,RQ_moveCW(A[i+1]-A[i]));}rep(i,N){auto g = G.get(i);//cout << "(" << g.minx << ", " << g.maxx << ", " << g.mindx << ", " << g.maxdx << ", " << g.dx << ")" << endl;}rep(i,Q){ll b,c; cin >> b >> c;b = (b+queryKey_D) % L;c = (c+queryKey_D) % 1'000'000'000'000'000;ll ans = -1;//cout << "b = "<< b << ", c = " << c << endl;int sp = ubound_A(c);//cout << "sp = " << sp << endl;if(sp == N + 1){//cout << "EASY" << endl;if(N%2 == 0) ans = b;else ans = L-b;}else if(sp%2 == 1 && A[sp] - c >= b){ans = b;}else if(sp%2 == 0 && A[sp] - c >= L-b){ans = L-b;}else{//cout << "HARDEST" << endl;RQS preq = RQe();if(sp != 0) preq = (sp%2 == 1) ? RQ_moveCCW(A[sp]-c) : RQ_moveCW(A[sp]-c);int spr = G.max_right(sp,[preq,b](RQS q)->bool {RQS qq = RQop(preq,q);return -b < qq.mindx && qq.maxdx < L-b;});//cout << "spr = " << spr << endl;preq = RQop(preq,G.prod(sp,spr));//cout << "preq = (" << preq.minx << ", " << preq.maxx << ", " << preq.mindx << ", " << preq.maxdx << ", " << preq.dx << ")" << endl;sp = spr;if(spr % 2 == 0) ans = (A[spr] - c) + (b + (preq.dx - preq.maxx));else ans = (A[spr] - c) + ((L-b) - (preq.dx - preq.minx));}queryKey_D = ans;cout << ans << "\n";}return 0;}struct ios_do_not_sync{ios_do_not_sync(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_inst;