#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define INF 1000000000
#define LINF 1000000000000000000
#define pb push_back
using namespace std;
#define MAXN 200010
ll a[MAXN];
ll seg[4*MAXN];
ll lazy[4*MAXN];
void propagate(int node, int l, int r){
if(l == r){
seg[node] += lazy[node];
lazy[node] = 0;
return;
}
lazy[2*node] += lazy[node]; lazy[2*node+1] += lazy[node];
lazy[node] = 0;
return;
}
void update(int node, int l, int r, int L, int R, ll x){
//cout << "START " << node << ", " << l << ", " << r << endl;
propagate(node, l, r);
if(L <= l && r <= R){
lazy[node] += x;
propagate(node, l, r);
//cout << "END2 " << node << ", " << l << ", " << r << endl;
return;
}
int mid = (l+r)/2;
if(L <= mid) update(2*node, l, mid, L, R, x);
if(R > mid) update(2*node+1, mid+1, r, L, R, x);
//cout << "END " << node << ", " << l << ", " << r << endl;
// propagate(2*node, l, mid);
// propagate(2*node+1, mid+1, r);
}
ll query(int node, int l, int r, int idx){
propagate(node, l, r);
if(l == r) return seg[node];
int mid = (l+r)/2;
if(idx <= mid) return query(2*node, l, mid, idx);
else return query(2*node+1, mid+1, r, idx);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, q; ll s, t;
cin >> n >> q >> s >> t; s = -s;
for(int i = 1; i <= n+1; i++){
cin >> a[i];
update(1, 1, n+1, i, i, a[i]);
}
/*cout << seg[1] << endl;
cout << seg[2] << " " << seg[3] << endl;
cout << seg[4] << " " << seg[5] << " " << seg[6] << " " << seg[7] << endl;*/
ll res = 0;
for(int i = 2; i <= n+1; i++){
if(a[i] > a[i-1]) res += s * (a[i]-a[i-1]);
else res += t * (a[i-1]-a[i]);
}
/// cout << "res: " << res << endl;
while(q--){
int l, r, x; cin >> l >> r >> x; l++, r++;
/** cout << query(1, 1, n+1, 1) << ", ";
cout << query(1, 1, n+1, 2) << ", ";
cout << query(1, 1, n+1, 3) << ", ";
cout << query(1, 1, n+1, 4) << endl;*/
int d = query(1, 1, n+1, l) - query(1, 1, n+1, l-1);
///cout << "dl: " << d << ", dl2: " << d+x << endl;
/*if(d > 0 && d+x <= 0) res += d*s+(x-d)*t;
else if(d <= 0 && d+x > 0) res -= (-d)*t+(d+x)*s;
else if(d > 0 && d+x > 0) res -= x*s;
else res += -x*t;*/
if(d > 0 && d+x <= 0){res -= d*s; res += -(d+x)*t;}
else if(d <= 0 && d+x > 0){res -= t*(-d); res += (d+x)*s;}
else if(d > 0 && d+x > 0){res -= s*d; res += s*(d+x);}
else{res -= t*(-d); res += (-d+x)*t;}
if(r < n+1){
d = query(1, 1, n+1, r+1) - query(1, 1, n+1, r);
///cout << "dr: " << d << ", dr2: " << d-x << endl;
/*if(d > 0 && d-x <= 0) res += d*s+(x-d)*t;
else if(d <= 0 && d-x > 0) res -= (-d)*t+(d-x)*s;
else if(d > 0 && d-x > 0) res -= -x*s;
else res += x*s;*/
if(d > 0 && d-x <= 0){res -= d*s; res += -(d-x)*t;}
else if(d <= 0 && d-x > 0){res -= (-d)*t; res += (d-x)*s;}
else if(d > 0 && d-x > 0){res -= d*s; res += (d-x)*s;}
else{res -= (-d)*t; res += -(d-x)*t;}
}
update(1, 1, n+1, l, r, x);
cout << res << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
606 ms |
16936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
