제출 #815809

#제출 시각아이디문제언어결과실행 시간메모리
815809OAleksaFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
193 ms17212 KiB
#include <bits/stdc++.h> //#include "factories.h" #define f first #define s second #define int long long using namespace std; const int maxn = 2e5 + 69; long long n, q, s, t, a[maxn], st[4 * maxn], f[maxn]; void upd(int v, int tl, int tr, int x, int d) { if(tl == tr) st[v] = d; else { int mid = (tl + tr) / 2; if(x <= mid) upd(v * 2, tl, mid, x, d); else upd(v * 2 + 1, mid + 1, tr, x, d); st[v] = st[v * 2] + st[v * 2 + 1]; } } void add(int v, int d) { for(int i = v;i < maxn;i += (i & -i)) f[i] += d; } int qry(int v) { int res = 0; for(int i = v;i >= 1;i -= (i & -i)) res += f[i]; return res; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tt = 1; //cin >> tt; while(tt--) { cin >> n >> q >> s >> t; for(int i = 0;i <= n;i++) cin >> a[i]; for(int i = 1;i <= n;i++) { if(a[i] > a[i - 1]) upd(1, 1, n, i, (a[i - 1] - a[i]) * s); else upd(1, 1, n, i, (a[i - 1] - a[i]) * t); } for(int i = 1;i <= q;i++) { int l, r, x; cin >> l >> r >> x; add(l, x); add(r + 1, -x); int levi = a[l] + qry(l); int desni = a[r] + qry(r); int kurac = 0; int josjedankurac = 0; if(l > 1) kurac = a[l - 1] + qry(l - 1); if(r < n) josjedankurac = a[r + 1] + qry(r + 1); if(levi > kurac) upd(1, 1, n, l, (kurac - levi) * s); else upd(1, 1, n, l, (kurac - levi) * t); if(r < n) { if(josjedankurac > desni) upd(1, 1, n, r + 1, (desni - josjedankurac) * s); else upd(1, 1, n, r + 1, (desni - josjedankurac) * t); } cout << st[1] << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...