이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// to speed up code, use fenwick!
#include <iostream>
#include <vector>
using namespace std;
#define maxn 200005
typedef long long ll;
int n,q; ll s,t;
ll gap(ll a, ll b) {
if (a < b) return (a-b) * s;
else return (a-b) * t;
}
ll a[maxn];
ll d[maxn]; // difference array, d[1] + d[2] + ... + d[i] == a[i]
ll z[maxn]; // fenwick for temperature
void inc(int i, ll x) {
for (; i <= n; i += i&(-i)) d[i] += x;
}
ll get(int i) {
ll ret = 0;
for (; i; i -= i&(-i)) ret += d[i];
return ret;
}
void aug(int i, ll x) {
for (; i <= n; i += i&(-i)) z[i] += x;
}
ll temp(int i) {
ll ret = 0;
for (; i; i -= i&(-i)) ret += z[i];
return ret;
}
int main() {
cin >> n >> q >> s >> t;
for (int i = 0; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) inc(i,a[i]-a[i-1]);
for (int i = 0; i < n; i++) aug(i+1,gap(get(i),get(i+1)));
for (int i = 0; i < q; i++) {
int l, r; ll x; cin >> l >> r >> x;
ll L = get(l-1), R = get(l);
ll u = gap(L,R), v = gap(L,R+x);
aug(l,v-u);
if (r != n) {
L = get(r), R = get(r+1);
u = gap(L,R), v = gap(L+x,R);
aug(r+1,v-u);
}
inc(l,x);
if (r != n) inc(r+1,-x);
cout << temp(n) << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |