#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 4e5;
ll Has[4 * N + 2], S[4 * N + 2];
ll a[N + 2];
void PushDown(int p, int lo, int hi) {
if (!Has[p] ) return ;
ll mid = (lo + hi)/2;
S[p] += (Has[p] * (hi - lo + 1));
Has[2 * p] += Has[p];
Has[2 * p + 1] += Has[p];
Has[p] = 0;
}
void Update(ll p, ll lo, ll hi, ll l, ll r, ll x) {
PushDown(p, lo, hi);
if ( lo > r || l > hi) return ;
if ( l <= lo && hi <= r) {
Has[p] = x;
return ;
}
ll mid = (lo + hi)/2;
Update(2 * p , lo , mid, l, r, x);
Update(2 * p + 1, mid +1, hi, l, r, x);
S[p] = S[2 * p] + S[2 * p + 1];
}
ll Find(ll p, ll lo, ll hi, ll x) {
PushDown(p, lo, hi);
if ( lo == hi) return S[p];
ll mid = (lo + hi)/2;
if ( x <= mid) return Find(2 * p, lo, mid, x);
return Find(2 * p + 1, mid + 1, hi, x);
}
void Build(ll p, ll lo, ll hi) {
if ( lo == hi) {
S[p] = a[lo];
return ;
}
ll mid = (lo + hi)/2;
Build(2 * p , lo , mid);
Build(2 * p + 1, mid + 1, hi);
S[p] = S[2 * p] + S[2 * p + 1];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
ll n, s, t, q, i, usult, buuralt,p, l, r, x;
cin >> n >> q >> s >> t;
usult = buuralt = 0;
for (i =0; i <= n; i ++) {
cin >> a[i];
if ( i == 0) continue;
if ( a[i] > a[i - 1]) usult += abs(a[i] - a[i - 1]);
else buuralt += abs(a[i - 1] - a[i]);
}
p =(buuralt * t) - (s * usult);
Build(1, 0, n);
for (i = 1; i <= q; i ++) {
cin >> l >> r >> x;
a[l - 1] = Find(1, 0, n, l - 1);
a[l] = Find(1, 0, n, l);
a[r] = Find(1, 0, n, r);
if ( r != n) a[r + 1] = Find(1, 0, n, r + 1);
if ( a[l] > a[l - 1]) usult -= abs(a[l] - a[l- 1]);
else buuralt -= abs(a[l] - a[l - 1]);
if ( r != n) {
if ( a[r] > a[r + 1]) buuralt -= abs(a[r] - a[r+1]);
else usult -= abs(a[r] - a[r + 1]);
}
Update(1, 0, n, l, r, x);
a[l - 1] = Find(1, 0, n, l - 1);
a[l] = Find(1, 0, n, l);
a[r] = Find(1, 0, n, r);
if ( r != n) a[r + 1] = Find(1, 0, n, r + 1);
if ( a[l] > a[l - 1]) usult += abs(a[l] - a[l- 1]);
else buuralt += abs(a[l] - a[l - 1]);
if ( r != n) {
if ( a[r] > a[r + 1]) buuralt += abs(a[r] - a[r+1]);
else usult += abs(a[r] - a[r + 1]);
}
p =(buuralt * t) - (s* usult);
cout << p << endl;
}
}
Compilation message
foehn_phenomena.cpp: In function 'void PushDown(int, int, int)':
foehn_phenomena.cpp:10:5: warning: unused variable 'mid' [-Wunused-variable]
10 | ll mid = (lo + hi)/2;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2392 KB |
Output is correct |
2 |
Correct |
5 ms |
2396 KB |
Output is correct |
3 |
Correct |
5 ms |
2396 KB |
Output is correct |
4 |
Correct |
6 ms |
2644 KB |
Output is correct |
5 |
Correct |
5 ms |
2396 KB |
Output is correct |
6 |
Correct |
5 ms |
2624 KB |
Output is correct |
7 |
Correct |
5 ms |
2396 KB |
Output is correct |
8 |
Correct |
5 ms |
2396 KB |
Output is correct |
9 |
Correct |
5 ms |
2396 KB |
Output is correct |
10 |
Correct |
5 ms |
2396 KB |
Output is correct |
11 |
Correct |
5 ms |
2396 KB |
Output is correct |
12 |
Correct |
5 ms |
2396 KB |
Output is correct |
13 |
Correct |
4 ms |
2396 KB |
Output is correct |
14 |
Correct |
4 ms |
2396 KB |
Output is correct |
15 |
Correct |
5 ms |
2624 KB |
Output is correct |
16 |
Correct |
4 ms |
2396 KB |
Output is correct |
17 |
Correct |
4 ms |
2392 KB |
Output is correct |
18 |
Correct |
5 ms |
2396 KB |
Output is correct |
19 |
Correct |
1 ms |
2396 KB |
Output is correct |
20 |
Correct |
1 ms |
2396 KB |
Output is correct |
21 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
585 ms |
19212 KB |
Output is correct |
2 |
Correct |
619 ms |
19920 KB |
Output is correct |
3 |
Correct |
593 ms |
20564 KB |
Output is correct |
4 |
Correct |
624 ms |
20024 KB |
Output is correct |
5 |
Correct |
588 ms |
20308 KB |
Output is correct |
6 |
Correct |
413 ms |
13908 KB |
Output is correct |
7 |
Correct |
418 ms |
13948 KB |
Output is correct |
8 |
Correct |
541 ms |
20916 KB |
Output is correct |
9 |
Correct |
534 ms |
21072 KB |
Output is correct |
10 |
Correct |
584 ms |
19724 KB |
Output is correct |
11 |
Correct |
409 ms |
14060 KB |
Output is correct |
12 |
Correct |
404 ms |
14104 KB |
Output is correct |
13 |
Correct |
411 ms |
14916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2392 KB |
Output is correct |
2 |
Correct |
5 ms |
2396 KB |
Output is correct |
3 |
Correct |
5 ms |
2396 KB |
Output is correct |
4 |
Correct |
6 ms |
2644 KB |
Output is correct |
5 |
Correct |
5 ms |
2396 KB |
Output is correct |
6 |
Correct |
5 ms |
2624 KB |
Output is correct |
7 |
Correct |
5 ms |
2396 KB |
Output is correct |
8 |
Correct |
5 ms |
2396 KB |
Output is correct |
9 |
Correct |
5 ms |
2396 KB |
Output is correct |
10 |
Correct |
5 ms |
2396 KB |
Output is correct |
11 |
Correct |
5 ms |
2396 KB |
Output is correct |
12 |
Correct |
5 ms |
2396 KB |
Output is correct |
13 |
Correct |
4 ms |
2396 KB |
Output is correct |
14 |
Correct |
4 ms |
2396 KB |
Output is correct |
15 |
Correct |
5 ms |
2624 KB |
Output is correct |
16 |
Correct |
4 ms |
2396 KB |
Output is correct |
17 |
Correct |
4 ms |
2392 KB |
Output is correct |
18 |
Correct |
5 ms |
2396 KB |
Output is correct |
19 |
Correct |
1 ms |
2396 KB |
Output is correct |
20 |
Correct |
1 ms |
2396 KB |
Output is correct |
21 |
Correct |
1 ms |
2396 KB |
Output is correct |
22 |
Correct |
585 ms |
19212 KB |
Output is correct |
23 |
Correct |
619 ms |
19920 KB |
Output is correct |
24 |
Correct |
593 ms |
20564 KB |
Output is correct |
25 |
Correct |
624 ms |
20024 KB |
Output is correct |
26 |
Correct |
588 ms |
20308 KB |
Output is correct |
27 |
Correct |
413 ms |
13908 KB |
Output is correct |
28 |
Correct |
418 ms |
13948 KB |
Output is correct |
29 |
Correct |
541 ms |
20916 KB |
Output is correct |
30 |
Correct |
534 ms |
21072 KB |
Output is correct |
31 |
Correct |
584 ms |
19724 KB |
Output is correct |
32 |
Correct |
409 ms |
14060 KB |
Output is correct |
33 |
Correct |
404 ms |
14104 KB |
Output is correct |
34 |
Correct |
411 ms |
14916 KB |
Output is correct |
35 |
Correct |
641 ms |
19760 KB |
Output is correct |
36 |
Correct |
615 ms |
21228 KB |
Output is correct |
37 |
Correct |
660 ms |
21680 KB |
Output is correct |
38 |
Correct |
669 ms |
21528 KB |
Output is correct |
39 |
Correct |
634 ms |
21468 KB |
Output is correct |
40 |
Correct |
616 ms |
21424 KB |
Output is correct |
41 |
Correct |
636 ms |
21244 KB |
Output is correct |
42 |
Correct |
590 ms |
21352 KB |
Output is correct |
43 |
Correct |
623 ms |
20684 KB |
Output is correct |
44 |
Correct |
583 ms |
21012 KB |
Output is correct |
45 |
Correct |
603 ms |
20912 KB |
Output is correct |
46 |
Correct |
598 ms |
21644 KB |
Output is correct |
47 |
Correct |
407 ms |
14340 KB |
Output is correct |
48 |
Correct |
364 ms |
14568 KB |
Output is correct |
49 |
Correct |
624 ms |
20872 KB |
Output is correct |
50 |
Correct |
373 ms |
14420 KB |
Output is correct |
51 |
Correct |
405 ms |
14420 KB |
Output is correct |
52 |
Correct |
406 ms |
14340 KB |
Output is correct |