This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
Zadanie: Foehn Phenomen
Autor: Tomasz Kwiatkowski
*/
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 7;
const int BASE = 1 << 18;
ll segTree[2*BASE + 7];
void Add(int l, int r, int val)
{
l += BASE - 1;
r += BASE + 1;
while (l/2 != r/2) {
if (l % 2 == 0)
segTree[l + 1] += val;
if (r % 2 == 1)
segTree[r - 1] += val;
l /= 2;
r /= 2;
}
}
ll Get(int i)
{
i += BASE;
ll res = segTree[i];
while (i /= 2)
res += segTree[i];
return res;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int n, q, s, t;
cin >> n >> q >> s >> t;
for (int i = 0; i <= n; ++i) {
int h;
cin >> h;
Add(i, i, h);
}
auto delta = [&](int i) {
if (i == n)
return (ll)0;
ll a = Get(i), b = Get(i + 1);
return (a - b) * (a < b ? s : t);
};
ll ans = 0;
for (int i = 0; i < n; ++i)
ans += delta(i);
for (int i = 0; i < q; ++i) {
int l, r, x;
cin >> l >> r >> x;
ans -= delta(l - 1);
ans -= delta(r);
Add(l, r, x);
ans += delta(l - 1);
ans += delta(r);
cout << ans << '\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... |