이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio\
ios_base::sync_with_stdio(0);\
cin.tie(0);\
cout.tie(0)\
#define int long long
struct fenwickTree{
int n;
vi BIT;
fenwickTree(int sz){
n = sz;
BIT.resize(n + 1, 0);
}
void update(int i, int v){
if(i == 0) return;
while(i <= n){
BIT[i] += v;
i += i & (-i);
}
}
int query(int l, int r){
if(l > r) return 0;
if(l != 1) return query(1, r) - query(1, l - 1);
int res = 0;
while(r > 0){
res += BIT[r];
r -= r & (-r);
}
return res;
}
};
const int sz = 2e5 + 5;
int n, q, x, y, l, r, k, res, a[sz];
signed main(){
cin >> n >> q >> x >> y;
fenwickTree t(n + 1);
for(int i = 1; i <= n + 1; i++){
cin >> a[i];
t.update(i, a[i] - t.query(1, i - 1));
if(i > 1){
if(a[i] <= a[i - 1]) res += y * (a[i - 1] - a[i]);
else res -= x * (a[i] - a[i - 1]);
}
}
while(q--){
cin >> l >> r >> k;
l++, r++;
if(l > 1 and t.query(1, l) <= t.query(1, l - 1)) res -= y * abs(t.query(1, l) - t.query(1, l - 1));
else if(l > 1) res += x * abs(t.query(1, l) - t.query(1, l - 1));
if(r < n + 1 and t.query(1, r + 1) < t.query(1, r)) res -= y * abs(t.query(1, r + 1) - t.query(1, r));
else if(r < n + 1) res += x * abs(t.query(1, r + 1) - t.query(1, r));
t.update(l, k), t.update(r + 1, -k);
if(l > 1 and t.query(1, l) <= t.query(1, l - 1)) res += y * abs(t.query(1, l) - t.query(1, l - 1));
else if(l > 1) res -= x * abs(t.query(1, l) - t.query(1, l - 1));
if(r < n + 1 and t.query(1, r + 1) <= t.query(1, r)) res += y * abs(t.query(1, r + 1) - t.query(1, r));
else if(r < n + 1) res -= x * abs(t.query(1, r + 1) - t.query(1, r));
cout << res << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |