이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
typedef long long i64;
using namespace std;
const int N = 2e5 + 5;
i64 a [N], temp [N];
struct FenwickTree {
vector<i64> bit;
const int L;
FenwickTree (int n) : L (n + 5) {
bit.clear();
bit.resize(L);
}
void update (int idx, i64 delta) {
for (; idx < L; idx += idx & (- idx)) {
bit[idx] += delta;
}
}
void range_update (int lo, int hi, i64 delta) {
update (lo, + delta);
update (hi + 1, - delta);
}
i64 query (int idx) {
i64 res = 0;
for (; idx > 0; idx -= idx & (- idx)) {
res += bit[idx];
}
return res;
}
};
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q, temp_aumentar, temp_diminuir;
cin >> n >> q >> temp_aumentar >> temp_diminuir;
++n;
for (int i = 0; i < n; i++) cin >> a[i];
temp[0] = 0;
for (int i = 1; i < n; i++) {
int d = a[i] - a[i - 1];
if (d >= 0) {
temp[i] = temp[i - 1] - 1LL * temp_aumentar * d;
} else {
temp[i] = temp[i - 1] - 1LL * temp_diminuir * d;
}
}
FenwickTree valores (n), somas (n);
for (int i = 1; i < n; i++) {
valores.range_update (i, i, a[i]);
somas.range_update (i, i, temp[i]);
}
while (q--) {
int l, r, delta;
cin >> l >> r >> delta;
i64 diff_inicial = somas.query (l);
i64 diff_final = somas.query (r + 1);
valores.range_update(l, r, delta);
// Atualizar [L - R]
long long diff = -1;
i64 d = valores.query (l) - valores.query (l - 1);
if (d >= 0) {
diff = somas.query(l - 1) - 1LL * temp_aumentar * d;
diff -= diff_inicial;
} else {
diff = somas.query(l - 1) - 1LL * temp_diminuir * d;
diff -= diff_inicial;
}
somas.range_update (l, r, diff);
// Atualizar [R + 1, MAX]
diff = -1;
d = valores.query (r + 1) - valores.query (r);
if (d >= 0) {
diff = somas.query(r) - 1LL * temp_aumentar * d;
diff -= diff_final;
} else {
diff = somas.query(r) - 1LL * temp_diminuir * d;
diff -= diff_final;
}
somas.range_update (r + 1, n + 1, diff);
cout << somas.query (n - 1) << '\n';
}
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... |