이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2e5+1;
const int TSIZE = 1 << 20;
ll T[TSIZE], a[MAXN], ans, n, q, s, t;
void build(int v, int l, int r) {
if (l == r) {
T[v]=a[l];
return;
}
int m=(l+r)/2;
build(2*v, l, m), build(2*v+1, m+1, r);
}
void update(int v, int l, int r, int ql, int qr, ll x) {
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
T[v]+=x;
return;
}
int m=(l+r)/2;
update(2*v, l, m, ql, qr, x), update(2*v+1, m+1, r, ql, qr, x);
}
ll query(int v, int l, int r, int p, ll c) {
if (l == r) return T[v]+c;
int m=(l+r)/2;
if (p <= m) return query(2*v, l, m, p, c+T[v]);
return query(2*v+1, m+1, r, p, c+T[v]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>q>>s>>t>>a[0];
for (int i=1; i<=n; ++i) cin>>a[i];
build(1, 0, n);
for (int i=0; i<n; ++i) {
if (a[i+1] > a[i]) ans-=s*(a[i+1]-a[i]);
else ans+=t*(a[i]-a[i+1]);
}
for (int i=1; i<=q; ++i) {
ll l, r, x;
cin>>l>>r>>x;
ll la=query(1, 0, n, l, 0), lla=query(1, 0, n, l-1, 0);
if (la > lla) ans+=s*(la-lla);
else ans-=t*(lla-la);
if (r < n) {
ll ra=query(1, 0, n, r, 0), rra=query(1, 0, n, r+1, 0);
if (rra > ra) ans+=s*(rra-ra);
else ans-=t*(ra-rra);
update(1, 0, n, l, r, x);
ra=query(1, 0, n, r, 0), rra=query(1, 0, n, r+1, 0);
if (rra > ra) ans-=s*(rra-ra);
else ans+=t*(ra-rra);
} else update(1, 0, n, l, r, x);
la=query(1, 0, n, l, 0), lla=query(1, 0, n, l-1, 0);
if (la > lla) ans-=s*(la-lla);
else ans+=t*(lla-la);
cout<<ans<<"\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |