제출 #529696

#제출 시각아이디문제언어결과실행 시간메모리
529696leu_nautFoehn Phenomena (JOI17_foehn_phenomena)C++14
0 / 100
379 ms15576 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5; const int MOD = 1e9 + 7; const ll oo = 1e18; int n,q,s,t; ll ST[4 * N + 5], lazy[N + 5], a[N + 5]; void down(int id) { int tmp = lazy[id]; lazy[id * 2] += tmp; lazy[id * 2 + 1] += tmp; ST[id * 2] += tmp; ST[id * 2 + 1] += tmp; lazy[id] = 0; } void upd(int id, int l, int r, int u, int v, int val) { if (r < u || v < l) return ; if (u <= l && r <= v) { ST[id] += val; lazy[id] += val; return ; } int mid = (l + r) >> 1; down(id); upd(id * 2,l,mid,u,v,val); upd(id * 2 + 1,mid + 1,r,u,v,val); ST[id] = max(ST[id * 2], ST[id * 2 + 1]); } int get(int id, int l, int r, int u, int v) { if (r < u || v < l) return 0; if (u <= l && r <= v) return ST[id]; int mid = (l + r) >> 1; down(id); return get(id * 2,l,mid,u,v) + get(id * 2 + 1,mid + 1,r,u,v); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> q >> s >> t; for (int i = 0; i <= n; ++i) cin >> a[i], upd(1,1,n,i,i,a[i]); ll sum = 0; for (int i = 0; i < n; ++i) { ll tmp = llabs(a[i] - a[i + 1]); if (a[i] < a[i + 1]) sum += -tmp * s; else sum += tmp * t; } for (int i = 1; i <= q; ++i) { int l,r,x; cin >> l >> r >> x; ll tmp = llabs(a[l] - a[l - 1]); if (a[l] > a[l - 1]) sum += tmp * s; else sum += -tmp * t; if (r != n) { tmp = llabs(a[r] - a[r + 1]); if (a[r] < a[r + 1]) sum += tmp * s; else sum += -tmp * t; } upd(1,1,n,l,r,x); a[l] = get(1,1,n,l,l); a[r] = get(1,1,n,r,r); //cout << a[l] << ' ' << a[r] << '\n'; tmp = llabs(a[l] - a[l - 1]); if (a[l] > a[l - 1]) sum += -tmp * s; else sum += tmp * t; if (r != n) { tmp = llabs(a[r] - a[r + 1]); if (a[r] < a[r + 1]) sum += -tmp * s; else sum += tmp * t; } cout << sum << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...