이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q, s, t, v[200002];
ll ts;
ll aib[200002];
void add(int nod, int val)
{
for(; nod <= n; nod += (nod & (-nod)))
aib[nod] += val;
}
ll compute(int nod)
{
ll ans = 0;
for(; nod; nod -= (nod & (-nod)))
ans += aib[nod];
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q >> s >> t;
for(int i = 0; i <= n; ++i)
cin >> v[i];
for(int i = 0; i < n; ++i)
if(v[i] < v[i+1])
ts = ts - 1LL * s * (v[i+1] - v[i]);
else
ts = ts + 1LL * t * (v[i] - v[i+1]);
for(; q; --q)
{
int st, dr, val;
cin >> st >> dr >> val;
if(v[st - 1] + compute(st - 1) < v[st] + compute(st))
ts = ts + 1LL * s * (v[st] + compute(st) - v[st - 1] - compute(st - 1));
else
ts = ts - 1LL * t * (v[st - 1] + compute(st - 1) - v[st] - compute(st));
if(dr != n)
{
if(v[dr] + compute(dr) < v[dr + 1] + compute(dr + 1))
ts = ts + 1LL * s * (v[dr + 1] + compute(dr + 1) - v[dr] - compute(dr));
else
ts = ts - 1LL * t * (v[dr] + compute(dr) - v[dr + 1] - compute(dr + 1));
}
add(st, val);
add(dr + 1, -val);
if(v[st - 1] + compute(st - 1) < v[st] + compute(st))
ts = ts - 1LL * s * (v[st] + compute(st) - v[st - 1] - compute(st - 1));
else
ts = ts + 1LL * t * (v[st - 1] + compute(st - 1) - v[st] - compute(st));
if(dr != n)
{
if(v[dr] + compute(dr) < v[dr + 1] + compute(dr + 1))
ts = ts - 1LL * s * (v[dr + 1] + compute(dr + 1) - v[dr] - compute(dr));
else
ts = ts + 1LL * t * (v[dr] + compute(dr) - v[dr + 1] - compute(dr + 1));
}
cout << ts << '\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... |