結果
問題 | No.631 Noelちゃんと電車旅行 |
ユーザー | mamekin |
提出日時 | 2018-02-04 13:47:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 384 ms / 2,000 ms |
コード長 | 4,374 bytes |
コンパイル時間 | 1,212 ms |
コンパイル使用メモリ | 109,684 KB |
実行使用メモリ | 8,192 KB |
最終ジャッジ日時 | 2024-10-02 09:36:37 |
合計ジャッジ時間 | 7,608 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 278 ms
6,820 KB |
testcase_01 | AC | 375 ms
8,064 KB |
testcase_02 | AC | 384 ms
8,192 KB |
testcase_03 | AC | 370 ms
8,064 KB |
testcase_04 | AC | 370 ms
8,192 KB |
testcase_05 | AC | 371 ms
8,064 KB |
testcase_06 | AC | 146 ms
6,820 KB |
testcase_07 | AC | 78 ms
6,816 KB |
testcase_08 | AC | 273 ms
7,936 KB |
testcase_09 | AC | 321 ms
6,816 KB |
testcase_10 | AC | 223 ms
7,936 KB |
testcase_11 | AC | 203 ms
6,820 KB |
testcase_12 | AC | 249 ms
8,064 KB |
testcase_13 | AC | 242 ms
6,820 KB |
testcase_14 | AC | 115 ms
6,820 KB |
testcase_15 | AC | 207 ms
6,816 KB |
testcase_16 | AC | 2 ms
6,816 KB |
testcase_17 | AC | 2 ms
6,816 KB |
testcase_18 | AC | 2 ms
6,816 KB |
testcase_19 | AC | 2 ms
6,820 KB |
testcase_20 | AC | 2 ms
6,816 KB |
ソースコード
#define _USE_MATH_DEFINES #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <complex> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> #include <iterator> using namespace std; class SegmentTree { public: typedef long long T1; typedef long long T2; // データの初期値、以下の条件を満たすこと // uniteData(v, INIT_DATA) == v static const T1 INIT_DATA; private: // 遅延の初期値、以下の条件を満たすこと // updateData(prev, size, INIT_DELAY) == prev // updateDelay(x, INIT_DELAY) == x static const T2 INIT_DELAY; // 長さがlenの区間における前回の計算結果prevに対して、 // 区間の各要素にパラメータxを用いた更新処理を適用した後の計算結果を返す T1 updateData(T1 prev, int len, T2 x){ return prev + x; } // パラメータx1,x2による2つの更新処理を順に適用した場合に対して、 // 同じ結果になるような1つの更新処理のパラメータを返す T2 updateDelay(T2 x1, T2 x2){ return x1 + x2; } // 2つの区間の計算結果v1,v2に対して、 // その2つの区間を統合した区間における計算結果を返す T1 uniteData(T1 v1, T1 v2){ return max(v1, v2); } int n; vector<T1> data; vector<T2> delay; void updateTree(int a, int b, int k, int l, int r, T2 x){ if(a <= l && r <= b){ data[k] = updateData(data[k], r - l + 1, x); delay[k] = updateDelay(delay[k], x); } else if(a <= r && l <= b){ int len = (r - l + 1) / 2; for(int i=0; i<2; ++i){ data[k*2+1+i] = updateData(data[k*2+1+i], len, delay[k]); delay[k*2+1+i] = updateDelay(delay[k*2+1+i], delay[k]); } delay[k] = INIT_DELAY; updateTree(a, b, k*2+1, l, (l+r)/2, x); updateTree(a, b, k*2+2, (l+r+1)/2, r, x); data[k] = uniteData(data[k*2+1], data[k*2+2]); } } T1 getValue(int a, int b, int k, int l, int r){ if(a <= l && r <= b){ return data[k]; } else if(a <= r && l <= b){ int len = (r - l + 1) / 2; for(int i=0; i<2; ++i){ data[k*2+1+i] = updateData(data[k*2+1+i], len, delay[k]); delay[k*2+1+i] = updateDelay(delay[k*2+1+i], delay[k]); } delay[k] = INIT_DELAY; T1 v1 = getValue(a, b, k*2+1, l, (l+r)/2); T1 v2 = getValue(a, b, k*2+2, (l+r+1)/2, r); return uniteData(v1, v2); } else{ return INIT_DATA; } } public: SegmentTree(int n0){ n = 1; while(n < n0) n *= 2; data.assign(2*n-1, INIT_DATA); delay.assign(2*n-1, INIT_DELAY); } SegmentTree(const vector<T1>& v) : SegmentTree((int)v.size()){ for(unsigned i=0; i<v.size(); ++i) data[n-1+i] = v[i]; for(int k=n-2; k>=0; --k) data[k] = uniteData(data[k*2+1], data[k*2+2]); } // 区間[a,b]の要素にパラメータxによる更新処理を適用 void update(int a, int b, T2 x){ updateTree(a, b, 0, 0, n-1, x); } // 区間[a,b]の計算結果を返す T1 get(int a, int b){ return getValue(a, b, 0, 0, n-1); } // a番目の要素をxで上書きする void set(int a, T1 x){ getValue(a, a, 0, 0, n-1); data[n-1+a] = x; updateTree(a, a, 0, 0, n-1, INIT_DELAY); } }; const SegmentTree::T1 SegmentTree::INIT_DATA = 0; const SegmentTree::T2 SegmentTree::INIT_DELAY = 0; int main() { int n; cin >> n; vector<long long> t(n-1); for(int i=0; i<n-1; ++i){ cin >> t[i]; t[i] += 3 * (n - 1 - i); } SegmentTree st(t); int m; cin >> m; while(--m >= 0){ int l, r; long long d; cin >> l >> r >> d; -- l; -- r; st.update(l, r, d); cout << st.get(0, n-2) << endl; } return 0; }