結果
問題 | No.631 Noelちゃんと電車旅行 |
ユーザー | 👑 はまやんはまやん |
提出日時 | 2018-01-05 23:30:05 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 156 ms / 2,000 ms |
コード長 | 3,167 bytes |
コンパイル時間 | 2,776 ms |
コンパイル使用メモリ | 173,932 KB |
実行使用メモリ | 12,516 KB |
最終ジャッジ日時 | 2024-04-10 07:47:44 |
合計ジャッジ時間 | 6,371 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 103 ms
11,624 KB |
testcase_01 | AC | 155 ms
12,432 KB |
testcase_02 | AC | 156 ms
12,356 KB |
testcase_03 | AC | 151 ms
12,288 KB |
testcase_04 | AC | 151 ms
12,508 KB |
testcase_05 | AC | 148 ms
12,516 KB |
testcase_06 | AC | 65 ms
11,920 KB |
testcase_07 | AC | 41 ms
12,108 KB |
testcase_08 | AC | 115 ms
12,172 KB |
testcase_09 | AC | 129 ms
11,948 KB |
testcase_10 | AC | 97 ms
12,080 KB |
testcase_11 | AC | 88 ms
12,192 KB |
testcase_12 | AC | 107 ms
12,268 KB |
testcase_13 | AC | 98 ms
11,760 KB |
testcase_14 | AC | 46 ms
11,688 KB |
testcase_15 | AC | 87 ms
11,984 KB |
testcase_16 | AC | 5 ms
11,580 KB |
testcase_17 | AC | 5 ms
11,680 KB |
testcase_18 | AC | 5 ms
11,512 KB |
testcase_19 | AC | 6 ms
11,512 KB |
testcase_20 | AC | 5 ms
11,584 KB |
ソースコード
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } //--------------------------------------------------------------------------------------------------- template<class V, int NV> struct LazySegTree { // [L,R) vector<V> dat, lazy; LazySegTree() { dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef); } void lazyupdate(int a, int b, V &v, int k, int l, int r){push(k,l,r);if(r<=a||b<=l)return; if(a<=l&&r<=b){setLazy(k,v);push(k,l,r);}else{lazyupdate(a,b,v,k*2+1,l,(l+r)/2); lazyupdate(a, b, v, k * 2 + 2, (l + r) / 2, r); comp(dat[k], dat[k*2+1],dat[k*2+2]);}} void get(int a, int b, int k, int l, int r, V &res) {push(k, l, r); if (r <= a || b <= l)return; if (a <= l && r <= b) {comp(res, res, dat[k]);return;}get(a,b,k*2+1,l,(l+r) / 2, res); get(a, b, k * 2 + 2, (l + r) / 2, r, res);} void lazyupdate(int a, int b, V v) { lazyupdate(a, b, v, 0, 0, NV); } V get(int a, int b) { V res = resdef;get(a, b, 0, 0, NV, res); return res;} void update(int a, V &v, int k, int l, int r) {push(k, l, r);if (!(l <= a and a < r)) return; if (l == a and a + 1 == r) {dat[k] = v;}else {int md = (l+r)/2;update(a,v,k*2+1,l,md); update(a, v, k * 2 + 2, md, r); comp(dat[k], dat[k * 2 + 1], dat[k * 2 + 2]);}} void update(int a, V v) { update(a, v, 0, 0, NV); } void naivedump(int a, int b) { rep(i, a, b) cout << get(i, i + 1) << " "; cout << endl;} // ---- Template -------------------------------------------------------------------------------- // 区間add,区間max const V def = 0, ldef = 0, resdef = 0; inline void comp(V &res, V &l, V &r) { res = max(l,r); } inline void setLazy(int i, V &v) { lazy[i] += v; } inline void push(int k, int l, int r) { dat[k] += lazy[k]; if (r - l > 1) { setLazy(k * 2 + 1, lazy[k]); setLazy(k * 2 + 2, lazy[k]); } lazy[k] = ldef; } }; /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ typedef long long ll; int N; ll T[101010]; int M; LazySegTree<ll, 1 << 18> st; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N - 1) cin >> T[i]; rep(i, 0, N - 1) st.update(i, T[i] + 3 * (N - i - 1)); cin >> M; rep(i, 0, M) { int L, R, D; cin >> L >> R >> D; L--; R--; st.lazyupdate(L, R + 1, D); ll ans = st.get(0, N); printf("%lld\n", ans); } }