#include<bits/stdc++.h>
#define inf 1e15 + 7
#define N 200005
#define ll long long
using namespace std;
ll n,q,up,down;
ll arr[N] , lazy[4*N] , node[4*N];
ll ans = 0;
void build_tree(ll i,ll l,ll r) {
if(l>r) return;
if(l==r) {
node[i] = arr[l];
return;
}
ll m = (l + r) / 2;
build_tree(2*i , l , m); m++;
build_tree(2*i+1 , m , r);
node[i] = max(node[2*i],node[2*i+1]);
}
void true_val(ll i,ll l,ll r) {
if(lazy[i]==0) return;
node[i] += lazy[i];
if(l!=r) {
lazy[2*i] += lazy[i];
lazy[2*i+1] += lazy[i];
}
lazy[i] = 0;
}
void update(ll i,ll l,ll r,ll a,ll b,ll val) {
true_val(i,l,r);
if(l>r || b<l || r<a) return;
if(a<=l && r<=b) {
node[i] += val;
if(l!=r) {
lazy[i*2] += val;
lazy[i*2+1] += val;
return;
}
return;
}
ll m = (l + r) / 2;
update(2*i , l , m , a , b , val); m++;
update(2*i+1 , m , r , a , b , val);
node[i] = max(node[2*i],node[2*i+1]);
}
ll get_max(ll i,ll l,ll r,ll a,ll b) {
true_val(i,l,r);
if(l>r || b<l || r<a) return -inf;
if(a<=l && r<=b) return node[i];
ll m = (l + r) / 2;
return max(get_max(2*i,l,m,a,b),get_max(2*i+1,m+1,r,a,b));
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>q>>down>>up;
for(ll i=0;i<=n;i++) {
cin>>arr[i];
lazy[i] = 0;
}
build_tree(1,1,n);
for(ll i=0;i<=n-1;i++) {
if(arr[i] < arr[i+1]) ans -= down * abs(arr[i] - arr[i+1]);
else ans += up * abs(arr[i] - arr[i+1]);
}
while(q--) {
ll l,r,x; cin>>l>>r>>x;
ll l1 = (l==1 ? 0 : get_max(1,1,n,l-1,l-1));
ll l2 = get_max(1,1,n,l,l);
if(l1<l2) ans += down * (l2-l1);
if(l1 >= l2) ans -= up * (l1-l2);
if(l1 >= l2 + x) {
ans += up * (l1-l2-x);
}
if(l1 < l2 + x) {
ans -= down * (l2+x-l1);
}
if(r <= n - 1) {
ll r1 = get_max(1,1,n,r,r);
ll r2 = get_max(1,1,n,r+1,r+1);
if(r1<r2) ans += down*(r2-r1);
if(r1>=r2) ans -= up*(r1-r2);
if(r1+x<r2) ans -= down*(r2-r1-x);
if(r1+x>=r2) ans += up * (r1+x-r2);
}
cout<<ans<<endl;
update(1,1,n,l,r,x);
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
504 KB |
Output is correct |
2 |
Correct |
11 ms |
504 KB |
Output is correct |
3 |
Correct |
12 ms |
504 KB |
Output is correct |
4 |
Correct |
11 ms |
632 KB |
Output is correct |
5 |
Correct |
11 ms |
504 KB |
Output is correct |
6 |
Correct |
11 ms |
504 KB |
Output is correct |
7 |
Correct |
11 ms |
504 KB |
Output is correct |
8 |
Correct |
13 ms |
504 KB |
Output is correct |
9 |
Correct |
11 ms |
508 KB |
Output is correct |
10 |
Correct |
11 ms |
504 KB |
Output is correct |
11 |
Correct |
11 ms |
504 KB |
Output is correct |
12 |
Correct |
13 ms |
504 KB |
Output is correct |
13 |
Correct |
9 ms |
504 KB |
Output is correct |
14 |
Correct |
10 ms |
504 KB |
Output is correct |
15 |
Correct |
11 ms |
504 KB |
Output is correct |
16 |
Correct |
10 ms |
504 KB |
Output is correct |
17 |
Correct |
9 ms |
504 KB |
Output is correct |
18 |
Correct |
10 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1054 ms |
11752 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
504 KB |
Output is correct |
2 |
Correct |
11 ms |
504 KB |
Output is correct |
3 |
Correct |
12 ms |
504 KB |
Output is correct |
4 |
Correct |
11 ms |
632 KB |
Output is correct |
5 |
Correct |
11 ms |
504 KB |
Output is correct |
6 |
Correct |
11 ms |
504 KB |
Output is correct |
7 |
Correct |
11 ms |
504 KB |
Output is correct |
8 |
Correct |
13 ms |
504 KB |
Output is correct |
9 |
Correct |
11 ms |
508 KB |
Output is correct |
10 |
Correct |
11 ms |
504 KB |
Output is correct |
11 |
Correct |
11 ms |
504 KB |
Output is correct |
12 |
Correct |
13 ms |
504 KB |
Output is correct |
13 |
Correct |
9 ms |
504 KB |
Output is correct |
14 |
Correct |
10 ms |
504 KB |
Output is correct |
15 |
Correct |
11 ms |
504 KB |
Output is correct |
16 |
Correct |
10 ms |
504 KB |
Output is correct |
17 |
Correct |
9 ms |
504 KB |
Output is correct |
18 |
Correct |
10 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Execution timed out |
1054 ms |
11752 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |