이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3;
int n, q, s, t, a[N];
int sz;
long long seg[4 * N];
void init() {
sz = 1;
while (sz <= n + 1) sz <<= 1;
}
void build(int x = 0, int lx = 0, int rx = sz) {
if (rx - lx == 1) {
if (lx <= n) seg[x] = a[lx];
return;
}
int mid = (lx + rx) >> 1;
build(2 * x + 1, lx, mid);
build(2 * x + 2, mid, rx);
}
void upd(int l, int r, int v, int x = 0, int lx = 0, int rx = sz) {
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r) {
seg[x] += v;
return;
}
int mid = (lx + rx) >> 1;
upd(l, r, v, 2 * x + 1, lx, mid);
upd(l, r, v, 2 * x + 2, mid, rx);
}
long long get(int p, int x = 0, int lx = 0, int rx = sz) {
if (rx - lx == 1) return seg[x];
int mid = (lx + rx) >> 1;
long long ans = seg[x];
if (p < mid) ans += get(p, 2 * x + 1, lx, mid);
else ans += get(p, 2 * x + 2, mid, rx);
return ans;
}
void solve() {
cin >> n >> q >> s >> t;
for (int i = 0; i <= n; ++i)
cin >> a[i];
long long cur_ans = 0;
for (int i = 0; i < n; ++i) {
if (a[i] < a[i + 1]) cur_ans -= 1LL * s * (a[i + 1] - a[i]);
else cur_ans += 1LL * t * (a[i] - a[i + 1]);
}
init(), build();
while (q--) {
int l, r, v; cin >> l >> r >> v;
long long k1 = get(l - 1), k2 = get(l);
long long z1 = get(r), z2 = LLONG_MIN;
if (r != n) z2 = get(r + 1);
upd(l, r + 1, v);
if (k1 < k2) cur_ans += 1LL * s * (k2 - k1);
else cur_ans -= 1LL * t * (k1 - k2);
if (z2 != LLONG_MIN) {
if (z1 < z2) cur_ans += 1LL * s * (z2 - z1);
else cur_ans -= 1LL * t * (z1 - z2);
}
k2 += v, z1 += v;
if (k1 < k2) cur_ans -= 1LL * s * (k2 - k1);
else cur_ans += 1LL * t * (k1 - k2);
if (z2 != LLONG_MIN) {
if (z1 < z2) cur_ans -= 1LL * s * (z2 - z1);
else cur_ans += 1LL * t * (z1 - z2);
}
cout << cur_ans << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |