#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int long long
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=(ll)a;i<=(ll)b;++i)
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
const int mxN = 2e5+7, base = 1<<18;
int a[mxN], tree[base<<1];
void init(int n){
rep(i,0,n) tree[i+base] = a[i];
}
void add(int l,int r,int x){
l += base-1;
r += base+1;
while(r-l > 1){
if(!(l&1)) tree[l+1] += x;
if(r&1) tree[r-1] += x;
l /= 2; r /= 2;
}
}
int que(int v){
v += base;
int res = tree[v];
while(v){
v /= 2;
res += tree[v];
}
return res;
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,q,s,t; cin >> n >> q >> s >> t;
rep(i,0,n) cin >> a[i];
init(n);
int rosnie = 0, spada = 0;
rep(i,1,n) if(a[i] > a[i-1]) rosnie += a[i]-a[i-1];
rep(i,1,n) if(a[i] < a[i-1]) spada += a[i-1]-a[i];
while(q--){
int l,r,x; cin >> l >> r >> x;
if(que(l) > que(l-1)) rosnie -= que(l)-que(l-1);
if(r < n) if(que(r+1) > que(r)) rosnie -= que(r+1)-que(r);
if(que(l) < que(l-1)) spada += que(l)-que(l-1);
if(r < n) if(que(r+1) < que(r)) spada += que(r+1)-que(r);
add(l,r,x);
if(que(l) > que(l-1)) rosnie += que(l)-que(l-1);
if(r < n) if(que(r+1) > que(r)) rosnie += que(r+1)-que(r);
if(que(l) < que(l-1)) spada -= que(l)-que(l-1);
if(r < n) if(que(r+1) < que(r)) spada -= que(r+1)-que(r);
cout << -rosnie*s + spada*t << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4440 KB |
Output is correct |
2 |
Correct |
4 ms |
4444 KB |
Output is correct |
3 |
Correct |
3 ms |
4444 KB |
Output is correct |
4 |
Correct |
2 ms |
4656 KB |
Output is correct |
5 |
Correct |
3 ms |
4660 KB |
Output is correct |
6 |
Correct |
3 ms |
4444 KB |
Output is correct |
7 |
Correct |
3 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
4440 KB |
Output is correct |
9 |
Correct |
3 ms |
4440 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
11 |
Correct |
2 ms |
4444 KB |
Output is correct |
12 |
Correct |
3 ms |
4444 KB |
Output is correct |
13 |
Correct |
2 ms |
4444 KB |
Output is correct |
14 |
Correct |
2 ms |
4628 KB |
Output is correct |
15 |
Correct |
3 ms |
4444 KB |
Output is correct |
16 |
Correct |
3 ms |
4444 KB |
Output is correct |
17 |
Correct |
2 ms |
4444 KB |
Output is correct |
18 |
Correct |
3 ms |
4440 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
12880 KB |
Output is correct |
2 |
Correct |
176 ms |
13360 KB |
Output is correct |
3 |
Correct |
180 ms |
14072 KB |
Output is correct |
4 |
Correct |
167 ms |
13456 KB |
Output is correct |
5 |
Correct |
181 ms |
14624 KB |
Output is correct |
6 |
Correct |
132 ms |
13700 KB |
Output is correct |
7 |
Correct |
108 ms |
13432 KB |
Output is correct |
8 |
Correct |
155 ms |
14492 KB |
Output is correct |
9 |
Correct |
158 ms |
14672 KB |
Output is correct |
10 |
Correct |
156 ms |
13368 KB |
Output is correct |
11 |
Correct |
141 ms |
13388 KB |
Output is correct |
12 |
Correct |
108 ms |
14056 KB |
Output is correct |
13 |
Correct |
106 ms |
14204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4440 KB |
Output is correct |
2 |
Correct |
4 ms |
4444 KB |
Output is correct |
3 |
Correct |
3 ms |
4444 KB |
Output is correct |
4 |
Correct |
2 ms |
4656 KB |
Output is correct |
5 |
Correct |
3 ms |
4660 KB |
Output is correct |
6 |
Correct |
3 ms |
4444 KB |
Output is correct |
7 |
Correct |
3 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
4440 KB |
Output is correct |
9 |
Correct |
3 ms |
4440 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
11 |
Correct |
2 ms |
4444 KB |
Output is correct |
12 |
Correct |
3 ms |
4444 KB |
Output is correct |
13 |
Correct |
2 ms |
4444 KB |
Output is correct |
14 |
Correct |
2 ms |
4628 KB |
Output is correct |
15 |
Correct |
3 ms |
4444 KB |
Output is correct |
16 |
Correct |
3 ms |
4444 KB |
Output is correct |
17 |
Correct |
2 ms |
4444 KB |
Output is correct |
18 |
Correct |
3 ms |
4440 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4496 KB |
Output is correct |
22 |
Correct |
176 ms |
12880 KB |
Output is correct |
23 |
Correct |
176 ms |
13360 KB |
Output is correct |
24 |
Correct |
180 ms |
14072 KB |
Output is correct |
25 |
Correct |
167 ms |
13456 KB |
Output is correct |
26 |
Correct |
181 ms |
14624 KB |
Output is correct |
27 |
Correct |
132 ms |
13700 KB |
Output is correct |
28 |
Correct |
108 ms |
13432 KB |
Output is correct |
29 |
Correct |
155 ms |
14492 KB |
Output is correct |
30 |
Correct |
158 ms |
14672 KB |
Output is correct |
31 |
Correct |
156 ms |
13368 KB |
Output is correct |
32 |
Correct |
141 ms |
13388 KB |
Output is correct |
33 |
Correct |
108 ms |
14056 KB |
Output is correct |
34 |
Correct |
106 ms |
14204 KB |
Output is correct |
35 |
Correct |
176 ms |
13140 KB |
Output is correct |
36 |
Correct |
191 ms |
14396 KB |
Output is correct |
37 |
Correct |
195 ms |
15172 KB |
Output is correct |
38 |
Correct |
181 ms |
14876 KB |
Output is correct |
39 |
Correct |
179 ms |
15064 KB |
Output is correct |
40 |
Correct |
179 ms |
14928 KB |
Output is correct |
41 |
Correct |
180 ms |
14756 KB |
Output is correct |
42 |
Correct |
183 ms |
14828 KB |
Output is correct |
43 |
Correct |
182 ms |
14236 KB |
Output is correct |
44 |
Correct |
185 ms |
14492 KB |
Output is correct |
45 |
Correct |
171 ms |
14964 KB |
Output is correct |
46 |
Correct |
196 ms |
15800 KB |
Output is correct |
47 |
Correct |
109 ms |
14164 KB |
Output is correct |
48 |
Correct |
173 ms |
14148 KB |
Output is correct |
49 |
Correct |
159 ms |
13168 KB |
Output is correct |
50 |
Correct |
134 ms |
13996 KB |
Output is correct |
51 |
Correct |
108 ms |
14416 KB |
Output is correct |
52 |
Correct |
142 ms |
14160 KB |
Output is correct |