結果
問題 | No.2821 A[i] ← 2A[j] - A[i] |
ユーザー | GOTKAKO |
提出日時 | 2024-07-26 21:56:38 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 98 ms / 1,500 ms |
コード長 | 4,813 bytes |
コンパイル時間 | 2,942 ms |
コンパイル使用メモリ | 221,888 KB |
実行使用メモリ | 15,556 KB |
最終ジャッジ日時 | 2024-07-26 21:56:50 |
合計ジャッジ時間 | 5,382 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 63 ms
14,908 KB |
testcase_02 | AC | 92 ms
15,252 KB |
testcase_03 | AC | 98 ms
15,556 KB |
testcase_04 | AC | 54 ms
9,584 KB |
testcase_05 | AC | 54 ms
9,708 KB |
testcase_06 | AC | 35 ms
6,944 KB |
testcase_07 | AC | 33 ms
6,940 KB |
testcase_08 | AC | 53 ms
9,280 KB |
testcase_09 | AC | 16 ms
6,944 KB |
testcase_10 | AC | 20 ms
6,940 KB |
testcase_11 | AC | 19 ms
6,944 KB |
testcase_12 | AC | 17 ms
6,940 KB |
testcase_13 | AC | 24 ms
6,940 KB |
testcase_14 | AC | 19 ms
6,940 KB |
testcase_15 | AC | 26 ms
6,940 KB |
testcase_16 | AC | 14 ms
6,944 KB |
testcase_17 | AC | 21 ms
6,940 KB |
testcase_18 | AC | 24 ms
6,940 KB |
testcase_19 | AC | 4 ms
6,940 KB |
testcase_20 | AC | 5 ms
6,940 KB |
testcase_21 | AC | 3 ms
6,944 KB |
testcase_22 | AC | 4 ms
6,940 KB |
testcase_23 | AC | 7 ms
6,944 KB |
testcase_24 | AC | 2 ms
6,944 KB |
testcase_25 | AC | 2 ms
6,944 KB |
testcase_26 | AC | 3 ms
6,940 KB |
testcase_27 | AC | 3 ms
6,944 KB |
testcase_28 | AC | 2 ms
6,940 KB |
testcase_29 | AC | 2 ms
6,944 KB |
testcase_30 | AC | 2 ms
6,940 KB |
testcase_31 | AC | 2 ms
6,940 KB |
testcase_32 | AC | 3 ms
6,940 KB |
testcase_33 | AC | 2 ms
6,944 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using SS = long long; class SegmentTree{ public: int siz = 1,n; vector<SS> dat; SS op(SS a, SS b){return gcd(a,b);} SS e(){return 0;} void renew (SS &a,SS x){ //a = op(a,x); a = x; //その他. } void make(int N){ while(siz < N) siz *= 2; n = N; dat.resize(siz*2,e()); } void make2(int N,vector<SS> &A){ make(N); for(int i=0; i<N; i++){ int pos = i+siz; dat.at(pos) = A.at(i); } for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1)); } void update(int pos,SS x){ pos = pos+siz; renew(dat.at(pos),x); while(pos != 1){ pos = pos/2; dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1)); } } SS findans(int l, int r){ SS retl = e(),retr = e(); l += siz,r += siz; while(l < r){ if(l&1) retl = op(retl,dat.at(l++)); if(r&1) retr = op(dat.at(--r),retr); l >>= 1; r >>= 1; } return op(retl,retr); } SS get(int pos){return dat.at(pos+siz);} SS rangeans(int l, int r){return findans(l,r);} SS allrange(){return dat.at(1);} //rightは) leftは[で 渡す&返す. int maxright(const function<bool(SS)> f,int l = 0){ l += siz; int r = n+siz; vector<int> ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okl = e(); for(int i=0; i<ls.size(); i++){ l = ls.at(i); SS now = op(okl,dat.at(l)); if(!f(now)){ while(l < siz){ l <<= 1; now = op(okl,dat.at(l)); if(f(now)){okl = now; l++;} } return l-siz; } okl = now; } for(int i=rs.size()-1; i>=0; i--){ l = rs.at(i); SS now = op(okl,dat.at(l)); if(!f(now)){ while(l < siz){ l <<= 1; now = op(okl,dat.at(l)); if(f(now)){okl = now; l++;} } return l-siz; } okl = now; } return n; } int minleft(const function<bool(SS)> f,int r = -1){ if(r == -1) r = n; int l = siz; r += siz; vector<int> ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okr = e(); for(int i=0; i<rs.size(); i++){ r = rs.at(i); SS now = op(dat.at(r),okr); if(!f(now)){ while(r < siz){ r <<= 1; r++; now = op(dat.at(r),okr); if(f(now)){okr = now; r--;} } return r+1-siz; } } for(int i=ls.size()-1; i>=0; i--){ r = ls.at(i); SS now = op(dat.at(r),okr); if(!f(now)){ while(r < siz){ r <<= 1; r++; now = op(dat.at(r),okr); if(f(now)){okr = now; r--;} } return r+1-siz; } } return 0; } //ノーマルセグ木.一年の時を経て漸く二分探索実装した. }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<long long> A(N); for(auto &a : A) cin >> a; SegmentTree Z; Z.make(N); queue<int> Q; for(int i=0; i<N; i++) Q.push(i); set<long long> S; map<long long,vector<int>> M; for(int i=0; i<N; i++){ long long a = A.at(i); if(!S.count(a)){ S.insert(a); auto itr = S.lower_bound(a); auto itr2 = itr; itr2++; if(itr != S.begin() && itr2 != S.end()){ itr--; long long diff = (*itr2)-(*itr); int p = M[diff].back(); M[diff].pop_back(); Z.update(p,0); Q.push(p); itr++; } if(itr != S.begin()){ itr--; long long diff = a-(*itr); int p = Q.front(); Q.pop(); Z.update(p,diff); M[diff].push_back(p); itr++; } if(itr2 != S.end()){ long long diff = (*itr2)-a; int p = Q.front(); Q.pop(); Z.update(p,diff); M[diff].push_back(p); } } cout << Z.allrange() << "\n"; } }