제출 #480852

#제출 시각아이디문제언어결과실행 시간메모리
480852ymmFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
216 ms11460 KiB
/// /// breakdown breakdown /// #include <bits/stdc++.h> #define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x) #define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x) typedef long long ll; using namespace std; const int N = 200'010; ll fen[N]; void add(int r, ll x) { while(r > 0) { fen[r] += x; r -= r&-r; } } void add(int l, int r, ll x) { add(r, x); add(l, -x); } ll get(int i) { ++i; ll ans = 0; while(i < N){ ans += fen[i]; i += i&-i; } return ans; } int n, q; ll s, t; inline ll foo(ll x, ll y){return x < y? (x-y)*s: (x-y)*t;} inline ll foo(int i){return i>n?0:foo(get(i-1),get(i));} ll up(int l, int r, ll x) { ll ans = foo(l)+foo(r); add(l,r,x); ans = foo(l)+foo(r)-ans; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> q >> s >> t; ll ans = 0; Loop(i,0,n+1) { int x; cin >> x; if(i) ans += up(i,i+1,x); } while(q--) { int l, r, x; cin >> l >> r >> x; ++r; ans += up(l,r,x); cout << ans << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...