제출 #894644

#제출 시각아이디문제언어결과실행 시간메모리
894644reginoxFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
401 ms18564 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2e5+3; struct segtree{ ll tree[maxn*4], lazy[maxn*4]; void reset(){ memset(tree, 0, sizeof(tree)); memset(lazy, 0, sizeof(lazy)); } void down(ll u){ ll t = lazy[u]; tree[u*2]+=t; tree[u*2+1]+=t; lazy[u*2]+=t; lazy[u*2+1]+=t; lazy[u]=0; } void upd(ll id, ll l, ll r, ll u, ll v, ll val){ if(l>r) return ; if(r<u||v<l) return ; if(u<=l && v>=r){ tree[id]+=val; lazy[id]+=val; return ; } down(id); ll mid = (l+r)>>1; upd(id*2, l, mid, u, v, val); upd(id*2+1, mid+1, r, u, v, val); tree[id]=tree[id*2]+tree[id*2+1]; } ll get(ll id, ll l, ll r, ll u){ if(u<l||r<u) return 0; if(l==r) return tree[id]; down(id); ll mid = (l+r)>>1; return get(id*2, l, mid, u) + get(id*2+1, mid+1, r, u); } } tree; ll n, q, s, t, x, sum, p, l, r, l1, l2, r1, r2, pl1, pl2, pr1, pr2; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q >> s >> t; for(ll i = 0; i <= n; i++){ cin >> x; if(i==0) continue; if(p<x) sum -= (x-p)*s; else sum += (p-x)*t; tree.upd(1, 1, n, i, i, x); p=x; } while(q--){ cin >> l >> r >> x; // cout << l << " " << r << "\n"; if(l==1) pl1=0; else pl1 = tree.get(1, 1, n, l-1); pl2 = tree.get(1, 1, n, l); pr1 = tree.get(1, 1, n, r); if(r==n) pr2 = pr1; else pr2 = tree.get(1, 1, n, r+1); // cout << pl1 << " " << pl2 << " " << pr1 << " " << pr2 << "\n"; tree.upd(1, 1, n, l, r, x); if(l==1) l1=0; else l1 = tree.get(1, 1, n, l-1); l2 = tree.get(1, 1, n, l); r1 = tree.get(1, 1, n, r); if(r==n) r2 = r1; else r2 = tree.get(1, 1, n, r+1); // cout << l1 << " " << l2 << " " << r1 << " " << r2 << "\n"; if(pl1 < pl2){ if(l1 < l2) sum += ((pl2 - pl1) - (l2 - l1))*s; else{ sum += (pl2 - pl1)*s; sum += (l1-l2)*t; } } else{ if(l1 > l2){ sum+=((l1-l2) - (pl1-pl2))*t; } else{ sum -= (pl1-pl2)*t; sum -= (l2 - l1)*s; } } // cout << sum << "\n"; if(pr1 < pr2){ if(r1 < r2) sum += ((pr2 - pr1) - (r2 - r1))*s; else{ sum += (pr2 - pr1)*s; sum += (r1-r2)*t; } } else{ if(r1 > r2){ sum+=((r1-r2) - (pr1-pr2))*t; } else{ sum -= (pr1-pr2)*t; sum -= (r2 - r1)*s; } } cout << sum << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...