結果
問題 | No.631 Noelちゃんと電車旅行 |
ユーザー | Kutimoti_T |
提出日時 | 2018-01-06 20:53:46 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 368 ms / 2,000 ms |
コード長 | 1,846 bytes |
コンパイル時間 | 1,075 ms |
コンパイル使用メモリ | 66,196 KB |
実行使用メモリ | 9,728 KB |
最終ジャッジ日時 | 2024-10-02 09:32:13 |
合計ジャッジ時間 | 7,112 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 266 ms
5,248 KB |
testcase_01 | AC | 360 ms
9,472 KB |
testcase_02 | AC | 368 ms
9,728 KB |
testcase_03 | AC | 365 ms
9,728 KB |
testcase_04 | AC | 367 ms
9,600 KB |
testcase_05 | AC | 367 ms
9,472 KB |
testcase_06 | AC | 144 ms
6,272 KB |
testcase_07 | AC | 76 ms
6,016 KB |
testcase_08 | AC | 268 ms
8,960 KB |
testcase_09 | AC | 325 ms
7,168 KB |
testcase_10 | AC | 223 ms
8,832 KB |
testcase_11 | AC | 205 ms
6,528 KB |
testcase_12 | AC | 251 ms
8,832 KB |
testcase_13 | AC | 237 ms
5,632 KB |
testcase_14 | AC | 109 ms
5,248 KB |
testcase_15 | AC | 199 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
ソースコード
#include <iostream> #include <vector> using namespace std; typedef long long ll; struct LazySegment{ int n; vector<ll> node,lazy; LazySegment(vector<ll>& v) { int sz = (int)v.size(); n = 1; while(n < sz) n*= 2; node.resize(2 * n - 1); lazy.resize(2 * n - 1,0); for(int i = 0;i < sz;i++) node[i + n - 1] = v[i] + (sz - i) * 3; for(int i = n - 2;i >=0;i--) node[i] = max(node[i * 2 + 1],node[i * 2 + 2]); } void eval(int k,int l,int r) { if(lazy[k] != 0) { node[k] += lazy[k]; if(r - l > 1) { lazy[2 * k + 1] += lazy[k]; lazy[2 * k + 2] += lazy[k]; } lazy[k] = 0; } } void add(int a,int b,ll x,int k = 0,int l = 0,int r = -1) { if(r < 0) r = n; eval(k,l,r); if(r <= a || b <= l) return; if(a <= l && r <= b) { lazy[k] += x; eval(k,l,r); } else { add(a,b,x,2 * k + 1,l,(l + r) / 2); add(a,b,x,2 * k + 2,(l + r) / 2,r); node[k] = max(node[2 * k + 1] , node[2 * k + 2]); } } ll getMax(int a,int b,int k = 0,int l = 0,int r = -1) { if(r < 0) r = n; eval(k,l,r); if(r <= a || b <= l) return -100000000; if(a <= l && r <= b) return node[k]; ll vl = getMax(a,b,2*k+1,l,(l + r)/2); ll vr = getMax(a,b,2*k+2,(l + r)/2,r); return max(vl,vr); } void Print() { cout << endl; ll cou = 1; for(int i = 0;i < node.size();i++) { if(i == cou) { cout << endl; cou = 2 * cou + 1; } cout << node[i] << "+" << lazy[i] << " "; } } }; int N; vector<ll> T; int M; int L[100001]; int R[100001]; ll D[100001]; int main() { cin >> N; T.resize(N - 1); for(int i = 0;i < N - 1;i++) { cin >> T[i]; } cin >> M; for(int i = 0;i < M;i++) { cin >> L[i] >> R[i] >> D[i]; } LazySegment seg(T); for(int i = 0;i < M;i++) { seg.add(L[i] - 1,R[i],D[i]); cout << seg.getMax(0,N) << endl; } return 0; }