제출 #33559

#제출 시각아이디문제언어결과실행 시간메모리
33559ubiratan37Foehn Phenomena (JOI17_foehn_phenomena)C++11
30 / 100
563 ms16732 KiB
#include <bits/stdc++.h> #define ROOT 1 using namespace std; #define int long long struct node{ int val; }; node tree[4*212345]; node lazy[4*212345]; node combine(node a, node b){ node res; res.val = a.val+b.val; return res; } void propagate(int root, int l , int r){ if(lazy[root].val == 0) return; tree[root].val += (r-l+1)*lazy[root].val; if(l != r){ lazy[2*root].val += lazy[root].val; lazy[2*root+1].val += lazy[root].val; } lazy[root].val = 0; return; } void range_update(int root, int l, int r, int a, int b, long long val){ if(l == a && r == b){ lazy[root].val+=val; return; } int m = (l+r)/2; if(b <= m) range_update(2*root, l, m, a, b, val); else if(m < a) range_update(2*root+1, m+1, r, a, b, val); else { range_update(2*root, l, m, a, m, val); range_update(2*root+1, m+1, r, m+1, b, val); } propagate(root, l , r); propagate(2*root, l, m); propagate(2*root+1, m+1, r); tree[root] = combine(tree[2*root], tree[2*root+1]); return; } node query(int root, int l, int r, int a, int b){ propagate(root, l, r); if(l == a && r == b) return tree[root]; int m = (l+r)/2; if(b <= m) return query(2*root, l, m, a, b); else if(m < a) return query(2*root+1, m+1, r, a, b); else { node left = query(2*root, l, m, a, m); node right = query(2*root+1, m+1, r, m+1, b); node ans = combine(left, right); return ans; } } int32_t main(){ int n,q,s,t; cin >> n >> q >> s >> t; n++; for(int i=0; i<4*212345; i++) tree[i].val = lazy[i].val = 0; int v[n]; for(int i=1; i<=n; i++){ cin >> v[i]; range_update(ROOT, 1, n, i, i,v[i]); } int ans = 0; for(int i=1; i<n; i++){ if(v[i] < v[i+1]) ans -= abs(v[i+1]-v[i])*s; else ans += abs(v[i+1]-v[i])*t; } while(q--){ int l,r,x; cin >> l >> r >> x; l++, r++; if(l > 1){ v[l-1] = query(ROOT, 1, n, l-1, l-1).val; v[l] = query(ROOT, 1, n, l, l).val; if(v[l-1] < v[l]) ans += abs(v[l] - v[l-1])*s; else ans -= abs(v[l] - v[l-1])*t; if(v[l-1] < v[l]+x) ans -= abs(v[l]+x - v[l-1])*s; else ans += abs(v[l]+x - v[l-1])*t; } if(r < n){ v[r] = query(ROOT, 1, n, r, r).val; v[r+1] = query(ROOT, 1, n, r+1, r+1).val; if(v[r] < v[r+1]) ans += abs(v[r] - v[r+1])*s; else ans -= abs(v[r] - v[r+1])*t; if(v[r]+x < v[r+1]) ans -= abs(v[r]+x - v[r+1])*s; else ans += abs(v[r]+x - v[r+1])*t; } range_update(ROOT, 1, n, l, r, x); cout << ans << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...