제출 #907593

#제출 시각아이디문제언어결과실행 시간메모리
907593androFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
409 ms24172 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 2e5 + 5; struct segtree{ int t[4*N]; int query(int v,int tl,int tr,int l,int r){ if(tl>r||tr<l)return 0; if(tl >= l &&tr<=r)return t[v]; int tm=(tl+tr)/2; return query(v*2,tl,tm,l,r)+query(v*2+1,tm+1,tr,l,r); } void update(int v,int tl,int tr,int index,int value){ if(tl==tr)t[v]=value; else { int tm=(tl+tr)/2; if(index<=tm)update(v*2,tl,tm,index,value); else update(v*2+1,tm+1,tr,index,value); t[v]=t[v*2]+t[v*2+1]; } } void update(int i, int v) { update(1, 0, N, i, v); } int query(int l, int r) { return query(1, 0, N, l, r); } }seg1, seg2; struct fenw { int t[N]; int query(int i) { i += 1; int ans = 0; while(i) { ans += t[i]; i -= i & - i; } return ans; } void update(int i, int v) { i += 1; while(i < N) { t[i] += v; i += i & - i; } } }fenw; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q, s, t; cin >> n >> q >> s >> t; vector<int> a(n + 1); for(int i = 0; i <= n; i++) { cin >> a[i]; } for(int i = 0; i < n; i++) { if(a[i] < a[i + 1]) { seg1.update(i, a[i + 1] - a[i]); seg2.update(i, 0); } else { seg2.update(i, a[i] - a[i + 1]); seg1.update(i, 0); } } for(int i = 0; i <= n; i++) { fenw.update(i, a[i]); fenw.update(i + 1, - a[i]); } while(q--) { int l, r, x; cin >> l >> r >> x; fenw.update(l, x); fenw.update(r + 1, - x); /** for(int i = l; i <= r; i++) { a[i] += x; } int u1 = 0; int u2 = 0; for(int i = 0; i < n; i++) { if(a[i] < a[i + 1]) { //u -= s * (a[i + 1] - a[i]); u1 += a[i + 1] - a[i]; } else { //u += t * (a[i] - a[i + 1]); u2 += a[i] - a[i + 1]; } } cout << u2 * t << " " << u1 * s << "\n";**/ if(l) { int idx = fenw.query(l - 1); int in = fenw.query(l); if(idx < in) { seg1.update(l - 1, in - idx); seg2.update(l - 1, 0); } else { seg1.update(l - 1, 0); seg2.update(l - 1, idx - in); } } if(l + 1 <= n) { int idx = fenw.query(l); int in = fenw.query(l + 1); if(idx < in) { seg1.update(l, in - idx); seg2.update(l, 0); } else { seg1.update(l, 0); seg2.update(l, idx - in); } } if(r) { int idx = fenw.query(r - 1); int in = fenw.query(r); if(idx < in) { seg1.update(r - 1, in - idx); seg2.update(r - 1, 0); } else { seg1.update(r - 1, 0); seg2.update(r - 1, idx - in); } } if(r + 1 <= n) { int idx = fenw.query(r); int in = fenw.query(r + 1); if(idx < in) { seg1.update(r, in - idx); seg2.update(r, 0); } else { seg1.update(r, 0); seg2.update(r, idx - in); } } cout << seg2.query(0, n - 1) * t - seg1.query(0, n - 1) * s << "\n"; } //cout << fenw2.query(n) * t - fenw1.query(n) * s; } /* mogu izvucem s i t pre zagrade jedino sto se menja jeste razlika izmedju r i r + 1 i l i l - 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...