#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll base = 1<<18;
ll tree[2*base];
void zmien(ll a, ll b, ll v){
a+=base-1;
b+=base+1;
while(a/2!=b/2){
if (!(a&1))tree[a+1]+=v;
if (b&1)tree[b-1]+=v;
a>>=1;
b>>=1;
}
}
ll sprawdz(ll v){
v+=base;
ll ans=0;
while(v){
ans+=tree[v];
v>>=1;
}
return ans;
}
ll cur=0,n,q,s,t;
void change_wind(ll v, ll diff){
if (v==n+1)return;
ll h1=sprawdz(v-1),h2=sprawdz(v);
if (h1<h2)cur+=(h2-h1)*s;
else cur+=(h2-h1)*t;
if (h1<h2+diff)cur-=(h2+diff-h1)*s;
else cur-=(h2+diff-h1)*t;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll a,b,c;
cin >> n >> q >> s >> t;
for (ll i = 0; i<=n; i++){
cin >> tree[base+i];
}
for (ll i = 1; i<=n; i++){
if ((tree[base+i]>tree[base+i-1]))cur-=(tree[base+i]-tree[base+i-1])*s;
else cur-=(tree[base+i]-tree[base+i-1])*t;
}
for (ll i = 1; i<=q; i++){
cin >> a >> b >> c;
change_wind(a,c);
change_wind(b+1,-c);
zmien(a,b,c);
cout << cur << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2844 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2520 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2516 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
108 ms |
10672 KB |
Output is correct |
| 2 |
Correct |
109 ms |
11348 KB |
Output is correct |
| 3 |
Correct |
112 ms |
11848 KB |
Output is correct |
| 4 |
Correct |
108 ms |
11344 KB |
Output is correct |
| 5 |
Correct |
113 ms |
12624 KB |
Output is correct |
| 6 |
Correct |
78 ms |
11400 KB |
Output is correct |
| 7 |
Correct |
81 ms |
11692 KB |
Output is correct |
| 8 |
Correct |
111 ms |
12264 KB |
Output is correct |
| 9 |
Correct |
119 ms |
12580 KB |
Output is correct |
| 10 |
Correct |
113 ms |
11604 KB |
Output is correct |
| 11 |
Correct |
71 ms |
11240 KB |
Output is correct |
| 12 |
Correct |
77 ms |
12088 KB |
Output is correct |
| 13 |
Correct |
79 ms |
12372 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2844 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2520 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2516 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
108 ms |
10672 KB |
Output is correct |
| 23 |
Correct |
109 ms |
11348 KB |
Output is correct |
| 24 |
Correct |
112 ms |
11848 KB |
Output is correct |
| 25 |
Correct |
108 ms |
11344 KB |
Output is correct |
| 26 |
Correct |
113 ms |
12624 KB |
Output is correct |
| 27 |
Correct |
78 ms |
11400 KB |
Output is correct |
| 28 |
Correct |
81 ms |
11692 KB |
Output is correct |
| 29 |
Correct |
111 ms |
12264 KB |
Output is correct |
| 30 |
Correct |
119 ms |
12580 KB |
Output is correct |
| 31 |
Correct |
113 ms |
11604 KB |
Output is correct |
| 32 |
Correct |
71 ms |
11240 KB |
Output is correct |
| 33 |
Correct |
77 ms |
12088 KB |
Output is correct |
| 34 |
Correct |
79 ms |
12372 KB |
Output is correct |
| 35 |
Correct |
108 ms |
10832 KB |
Output is correct |
| 36 |
Correct |
111 ms |
12400 KB |
Output is correct |
| 37 |
Correct |
114 ms |
13136 KB |
Output is correct |
| 38 |
Correct |
116 ms |
13260 KB |
Output is correct |
| 39 |
Correct |
115 ms |
12880 KB |
Output is correct |
| 40 |
Correct |
118 ms |
12884 KB |
Output is correct |
| 41 |
Correct |
123 ms |
12720 KB |
Output is correct |
| 42 |
Correct |
113 ms |
12880 KB |
Output is correct |
| 43 |
Correct |
114 ms |
12116 KB |
Output is correct |
| 44 |
Correct |
110 ms |
12624 KB |
Output is correct |
| 45 |
Correct |
106 ms |
12628 KB |
Output is correct |
| 46 |
Correct |
116 ms |
13648 KB |
Output is correct |
| 47 |
Correct |
79 ms |
12112 KB |
Output is correct |
| 48 |
Correct |
75 ms |
12012 KB |
Output is correct |
| 49 |
Correct |
99 ms |
11092 KB |
Output is correct |
| 50 |
Correct |
81 ms |
11840 KB |
Output is correct |
| 51 |
Correct |
98 ms |
12368 KB |
Output is correct |
| 52 |
Correct |
104 ms |
12116 KB |
Output is correct |
