結果
問題 | No.900 aδδitivee |
ユーザー | kappybar |
提出日時 | 2020-07-16 17:30:34 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 326 ms / 2,000 ms |
コード長 | 3,525 bytes |
コンパイル時間 | 2,049 ms |
コンパイル使用メモリ | 181,808 KB |
実行使用メモリ | 30,972 KB |
最終ジャッジ日時 | 2023-08-16 12:16:32 |
合計ジャッジ時間 | 14,991 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 17 ms
24,576 KB |
testcase_01 | AC | 16 ms
24,840 KB |
testcase_02 | AC | 17 ms
24,528 KB |
testcase_03 | AC | 17 ms
24,528 KB |
testcase_04 | AC | 17 ms
24,604 KB |
testcase_05 | AC | 17 ms
24,748 KB |
testcase_06 | AC | 17 ms
24,524 KB |
testcase_07 | AC | 326 ms
27,292 KB |
testcase_08 | AC | 323 ms
27,352 KB |
testcase_09 | AC | 322 ms
27,240 KB |
testcase_10 | AC | 320 ms
27,272 KB |
testcase_11 | AC | 322 ms
27,236 KB |
testcase_12 | AC | 324 ms
27,328 KB |
testcase_13 | AC | 322 ms
27,184 KB |
testcase_14 | AC | 319 ms
27,240 KB |
testcase_15 | AC | 322 ms
27,212 KB |
testcase_16 | AC | 324 ms
27,176 KB |
testcase_17 | AC | 322 ms
27,240 KB |
testcase_18 | AC | 326 ms
27,336 KB |
testcase_19 | AC | 323 ms
27,172 KB |
testcase_20 | AC | 323 ms
27,168 KB |
testcase_21 | AC | 323 ms
27,416 KB |
testcase_22 | AC | 303 ms
30,884 KB |
testcase_23 | AC | 302 ms
30,908 KB |
testcase_24 | AC | 315 ms
30,884 KB |
testcase_25 | AC | 304 ms
30,972 KB |
testcase_26 | AC | 306 ms
30,956 KB |
testcase_27 | AC | 305 ms
30,884 KB |
testcase_28 | AC | 303 ms
30,944 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; constexpr int INF = 1e9; constexpr long long LINF = 1e17; constexpr int MOD = 1000000007; constexpr double PI = 3.14159265358979323846; template<typename Mono,typename Ope> struct LazySegmentTree{ using F = function<Mono(Mono,Mono)>; using G = function<Mono(Mono,Ope)>; using H = function<Ope(Ope,Ope)>; int n,height; F f; G g; H h; Mono tu; Ope eu; vector<Mono> node; vector<Ope> lazy; LazySegmentTree(F f,G g,H h,Mono tu,Ope eu):f(f),g(g),h(h),tu(tu),eu(eu){} void init(vector<Mono> v){ int n_ = (int)(v.size()); n = 1;height = 0; while(n < n_) n <<= 1,++ height; node.assign(2*n,tu); lazy.assign(2*n,eu); for(int i=0;i<n_;i++) node[i+n] = v[i]; for(int i=n-1;i>0;i--) node[i] = f(node[i<<1],node[i<<1|1]); } Mono eval(int k){ return (lazy[k]==eu)?node[k]:g(node[k],lazy[k]); } void prop(int k){ if(lazy[k]==eu) return; lazy[k<<1] = h(lazy[k<<1],lazy[k]); lazy[k<<1|1] = h(lazy[k<<1|1],lazy[k]); node[k] = eval(k); lazy[k] = eu; } void prop_above(int k){ for(int i=height;i>0;i--) prop(k>>i); } void recalc_above(int k){ while(k>0){ k >>= 1; node[k] = f(eval(k<<1),eval(k<<1|1)); } } void set_val(int k,Mono x){ k += n; prop_above(k); node[k] = x; lazy[k] = eu; recalc_above(k); } void update(int l,int r,Ope x){ if(l >= r) return; l += n;r += n-1; prop_above(l); prop_above(r); int a = l,b = r; ++ r; while(l < r){ if(l&1) lazy[l] = h(lazy[l],x), ++l; if(r&1) --r, lazy[r] = h(lazy[r],x); l >>= 1;r >>= 1; } recalc_above(a); recalc_above(b); } Mono query(int l,int r){ if(l >= r) return tu; l += n;r += n-1; prop_above(l); prop_above(r);++r; Mono vl = tu,vr = tu; while(l < r){ if(l&1) vl = f(vl,eval(l)), ++l; if(r&1) --r, vr = f(eval(r),vr); l >>= 1;r >>= 1; } return f(vl,vr); } }; int n = 100005; vector<pll> vv(2*n,pll(0,0)); vector<int> l(n); vector<int> r(n); vector<vector<pll>> tree(n,vector<pll>()); int idx=1; void dfs(int i,int &idx){ l[i] = idx; for(pll v:tree[i]){ vv[idx++] = pll(v.first,1); dfs(v.second,idx); vv[idx++] = pll(-v.first,-1); } r[i] = idx; } int main(){ auto f = [](pll a,pll b){ a.first+=b.first; a.second+=b.second; return a; }; auto g = [](pll a,ll b){ a.first += b*a.second; return a; }; auto h = [](ll a,ll b){ return a+b; }; LazySegmentTree<pll,ll> seg(f,g,h,pll(0,0),0); cin >> n; rep(i,n-1){ int u,v; ll w; cin >> u >> v >> w; tree[u].push_back(pll(w,v)); } dfs(0,idx); seg.init(vv); int q; cin >> q; while(q--){ int t; cin >> t; if(t==1){ int a; ll x; cin >> a >> x; seg.update(l[a],r[a],x); }else{ int b; cin >> b; cout << seg.query(0,r[b]).first << endl; } } return 0; }