結果
問題 | No.631 Noelちゃんと電車旅行 |
ユーザー | imulan |
提出日時 | 2018-01-05 22:43:35 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 281 ms / 2,000 ms |
コード長 | 2,479 bytes |
コンパイル時間 | 1,688 ms |
コンパイル使用メモリ | 171,020 KB |
実行使用メモリ | 8,192 KB |
最終ジャッジ日時 | 2024-04-10 07:43:28 |
合計ジャッジ時間 | 6,704 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 192 ms
6,812 KB |
testcase_01 | AC | 263 ms
8,064 KB |
testcase_02 | AC | 272 ms
8,064 KB |
testcase_03 | AC | 262 ms
8,192 KB |
testcase_04 | AC | 268 ms
8,064 KB |
testcase_05 | AC | 281 ms
8,064 KB |
testcase_06 | AC | 109 ms
6,940 KB |
testcase_07 | AC | 58 ms
6,944 KB |
testcase_08 | AC | 200 ms
7,936 KB |
testcase_09 | AC | 234 ms
6,944 KB |
testcase_10 | AC | 168 ms
7,808 KB |
testcase_11 | AC | 147 ms
6,944 KB |
testcase_12 | AC | 182 ms
8,064 KB |
testcase_13 | AC | 172 ms
6,940 KB |
testcase_14 | AC | 82 ms
6,940 KB |
testcase_15 | AC | 155 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,940 KB |
testcase_17 | AC | 2 ms
6,944 KB |
testcase_18 | AC | 2 ms
6,944 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 2 ms
6,944 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second #define dbg(x) cout<<#x" = "<<((x))<<endl template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;} template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;} struct LazySegTree{ int n; vector<ll> dat,lazy; //初期化 LazySegTree(int _n){ n=1; while(n<_n) n*=2; dat=vector<ll>(2*n-1,0); lazy=vector<ll>(2*n-1,0); } void show() { rep(j,dat.size()) printf(" %d: dat= %lld, lazy= %lld\n", j,dat[j],lazy[j]); } void setLazy(int k, ll v){ lazy[k] += v; dat[k] += v; } void push(int k, int l, int r){ if(lazy[k]!=0){ setLazy(2*k+1,lazy[k]); setLazy(2*k+2,lazy[k]); } lazy[k]=0; } void fix(int k, int l, int r){ dat[k]=max(dat[2*k+1],dat[2*k+2]); } ll merge(ll x, ll y){ return max(x,y); } //内部的に投げられるクエリ void _add(int a, int b, ll x, int k, int l, int r){ if(r<=a || b<=l) return; if(a<=l && r<=b){ setLazy(k,x); return; } push(k,l,r); _add(a,b,x,2*k+1,l,(l+r)/2); _add(a,b,x,2*k+2,(l+r)/2,r); fix(k,l,r); } //[a,b)に+x void add(int a, int b, ll x){ return _add(a,b,x,0,0,n); } //内部的に投げられるクエリ ll _query(int a, int b, int k, int l, int r){ if(r<=a || b<=l) return LLONG_MIN/3; if(a<=l && r<=b) return dat[k]; push(k,l,r); ll vl=_query(a,b,2*k+1,l,(l+r)/2); ll vr=_query(a,b,2*k+2,(l+r)/2,r); return merge(vl,vr); } //[a,b) ll query(int a, int b){ return _query(a,b,0,0,n); } }; int main(){ cin.tie(0);ios::sync_with_stdio(false); int n; cin >>n; vector<ll> t(n-1); rep(i,n-1) cin >>t[i]; LazySegTree T(n-1); ll a=3; for(int i=n-2; i>=0; --i){ T.add(i,i+1,t[i]+a); a+=3; } int m; cin >>m; while(m--){ int l,r,d; cin >>l >>r >>d; --l; --r; T.add(l,r+1,d); cout << T.query(0,n) << endl; } return 0; }