제출 #359228

#제출 시각아이디문제언어결과실행 시간메모리
359228PetyFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
182 ms13420 KiB
#include <bits/stdc++.h> using namespace std; ifstream fin ("echilibru.in"); ofstream fout ("echilibru.out"); typedef long long ll; int n, q; ll aib[200002], a[200002], s, t; ll query (int x) { ll s = 0; for (int i = x; i; i -= (i & -i)) s += aib[i]; return s; } void update (int x, ll val) { if (x > n) return; for (int i = x; i <= n; i += (i & -i)) aib[i] += val; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> q >> s >> t; n++; for (int i = 1; i <= n; i++) { cin >> a[i]; update(i, a[i]); update(i + 1, -a[i]); } ll sum = 0; for (int i = 1; i < n; i++) { if (a[i] < a[i + 1]) sum += (a[i] - a[i + 1]) * s; else sum += (a[i] - a[i + 1]) * t; } ll l, r, x; while (q--) { cin >> l >> r >> x; l++;r++; if (l > 1) { ll val1 = query(l), val2 = query(l - 1); if (val2 < val1) sum -= (val2 - val1) * s; else sum -= (val2 - val1) * t; } if (r < n) { ll val1 = query(r + 1), val2 = query(r); if (val2 < val1) sum -= (val2 - val1) * s; else sum -= (val2 - val1) * t; } update(l, x); update(r + 1, -x); if (l > 1) { ll val1 = query(l), val2 = query(l - 1); if (val2 < val1) sum += (val2 - val1) * s; else sum += (val2 - val1) * t; } if (r < n) { ll val1 = query(r + 1), val2 = query(r); if (val2 < val1) sum += (val2 - val1) * s; else sum += (val2 - val1) * t; } cout << sum << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...