#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define double long double
#define order_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
///* __ __ __ */
///* ====== _ /| /| __ _ / | | /| | @ | | | | / /| |\ | / | | @ | / */
///* \- || |_| |_ / |/ | | | |_ |- | |--| /-| | | \ \ |==| |- /=| | \ | | |--| | |- */
///* || | | |_ / | |__| _| |_ \__ | | / | |__ | __| | | | \ / | | \| \__ | | | | \ */
///*
typedef vector<int> vi;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vi> vv;
const int N = 2e5+4, inf = 1e8;
int a[N];
int b[N*3]{};
void push(int i, int l, int r){
if(l == r){
a[l] += b[i];
b[i] = 0;
return;
}
b[i*2] += b[i];
b[i*2+1] += b[i];
b[i]=0;
}
void upd(int i, int l, int r, int tl, int tr, int sum){
push(i, l, r);
if(l > tr || r < tl || r < l)return;
if(tl <= l && r <= tr){
b[i] += sum;
return;
}
int m = (l+r)>>1;
upd(i*2, l, m, tl, tr, sum);
upd(i*2+1, m+1, r, tl, tr, sum);
}
void get(int i, int l, int r, int pos){
if(pos==0)return;
push(i, l, r);
if(l == r && l == pos)return;
int m = (l+r)>>1;
if(pos <= m)get(i*2, l, m, pos);
else get(i*2+1, m+1, r, pos);
}
void solve(){
int n, q, s, t;
cin >> n >> q >> s >> t;
for(int i = 0; i <= n; i++){
cin >> a[i];
}
int ans = 0;
for(int i = 1; i <= n; i++){
int df = a[i-1]-a[i];
if(df > 0)ans += df*t;
else ans += df*s;
}
while(q--){
int l, r, x;
cin >> l >> r >> x;
get(1, 1, n, l);
get(1, 1, n, l-1);
int df = a[l-1]-a[l];
if(df > 0)ans -= df*t;
else ans -= df*s;
if(r < n){
get(1, 1, n, r);
get(1, 1, n, r+1);
int df = a[r]-a[r+1];
if(df > 0)ans -= df*t;
else ans -= df*s;
}
upd(1, 1, n, l, r, x);
get(1, 1, n, l);
get(1, 1, n, l-1);
int nwd = a[l-1] - a[l];
if(nwd > 0)ans += nwd*t;
else ans += nwd*s;
if(r < n){
get(1, 1, n, r);
get(1, 1, n, r+1);
int nwd = a[r] - a[r+1];
if(nwd > 0)ans += nwd*t;
else ans += nwd*s;
}
cout << ans << '\n';
}
}
main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int test = 1;
//~ cin >> test;
while(test--){
solve();
}
}
Compilation message
foehn_phenomena.cpp:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
105 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
344 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
344 KB |
Output is correct |
5 |
Correct |
3 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
600 KB |
Output is correct |
8 |
Correct |
2 ms |
344 KB |
Output is correct |
9 |
Correct |
2 ms |
344 KB |
Output is correct |
10 |
Correct |
2 ms |
344 KB |
Output is correct |
11 |
Correct |
3 ms |
600 KB |
Output is correct |
12 |
Correct |
2 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
2 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
344 KB |
Output is correct |
16 |
Correct |
2 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
2 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
271 ms |
13136 KB |
Output is correct |
2 |
Correct |
292 ms |
13788 KB |
Output is correct |
3 |
Correct |
286 ms |
14136 KB |
Output is correct |
4 |
Correct |
299 ms |
13608 KB |
Output is correct |
5 |
Correct |
292 ms |
14832 KB |
Output is correct |
6 |
Correct |
105 ms |
11604 KB |
Output is correct |
7 |
Correct |
109 ms |
11672 KB |
Output is correct |
8 |
Correct |
248 ms |
14756 KB |
Output is correct |
9 |
Correct |
251 ms |
14904 KB |
Output is correct |
10 |
Correct |
259 ms |
13708 KB |
Output is correct |
11 |
Correct |
165 ms |
11556 KB |
Output is correct |
12 |
Correct |
105 ms |
12184 KB |
Output is correct |
13 |
Correct |
172 ms |
12448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
344 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
3 ms |
344 KB |
Output is correct |
5 |
Correct |
3 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
600 KB |
Output is correct |
8 |
Correct |
2 ms |
344 KB |
Output is correct |
9 |
Correct |
2 ms |
344 KB |
Output is correct |
10 |
Correct |
2 ms |
344 KB |
Output is correct |
11 |
Correct |
3 ms |
600 KB |
Output is correct |
12 |
Correct |
2 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
2 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
344 KB |
Output is correct |
16 |
Correct |
2 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
2 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
271 ms |
13136 KB |
Output is correct |
23 |
Correct |
292 ms |
13788 KB |
Output is correct |
24 |
Correct |
286 ms |
14136 KB |
Output is correct |
25 |
Correct |
299 ms |
13608 KB |
Output is correct |
26 |
Correct |
292 ms |
14832 KB |
Output is correct |
27 |
Correct |
105 ms |
11604 KB |
Output is correct |
28 |
Correct |
109 ms |
11672 KB |
Output is correct |
29 |
Correct |
248 ms |
14756 KB |
Output is correct |
30 |
Correct |
251 ms |
14904 KB |
Output is correct |
31 |
Correct |
259 ms |
13708 KB |
Output is correct |
32 |
Correct |
165 ms |
11556 KB |
Output is correct |
33 |
Correct |
105 ms |
12184 KB |
Output is correct |
34 |
Correct |
172 ms |
12448 KB |
Output is correct |
35 |
Correct |
301 ms |
13432 KB |
Output is correct |
36 |
Correct |
284 ms |
14672 KB |
Output is correct |
37 |
Correct |
276 ms |
15440 KB |
Output is correct |
38 |
Correct |
282 ms |
15184 KB |
Output is correct |
39 |
Correct |
286 ms |
15312 KB |
Output is correct |
40 |
Correct |
287 ms |
15184 KB |
Output is correct |
41 |
Correct |
279 ms |
15184 KB |
Output is correct |
42 |
Correct |
284 ms |
15072 KB |
Output is correct |
43 |
Correct |
284 ms |
14460 KB |
Output is correct |
44 |
Correct |
290 ms |
14916 KB |
Output is correct |
45 |
Correct |
283 ms |
14928 KB |
Output is correct |
46 |
Correct |
294 ms |
15952 KB |
Output is correct |
47 |
Correct |
104 ms |
12296 KB |
Output is correct |
48 |
Correct |
158 ms |
12156 KB |
Output is correct |
49 |
Correct |
282 ms |
13392 KB |
Output is correct |
50 |
Correct |
156 ms |
11988 KB |
Output is correct |
51 |
Correct |
105 ms |
12368 KB |
Output is correct |
52 |
Correct |
267 ms |
14160 KB |
Output is correct |