#include <bits/stdc++.h>
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, q, s, t;
int a[N];
LL ans = 0;
struct FenwickTree {
LL fw[N];
void Update(int l, int r, int v) {
for (l; l <= n; l += l & -l) fw[l] += v;
++r;
for (r; r <= n; r += r & -r) fw[r] -= v;
}
LL Query(int i) {
LL ans = 0;
for (i; i > 0; i -= i & -i) ans += fw[i];
return ans;
}
} FT;
void Change(LL v1, LL v2, int d) {
if (v1 < v2) ans += d * (LL)s * (v1 - v2);
else ans += d * (LL)t * (v1 - v2);
}
void Update(int l, int r, int x) {
if (r < n) {
LL v1 = a[r] + FT.Query(r), v2 = a[r + 1] + FT.Query(r + 1);
Change(v1, v2, -1);
v1 += x;
Change(v1, v2, +1);
}
LL v1 = a[l - 1] + FT.Query(l - 1), v2 = a[l] + FT.Query(l);
Change(v1, v2, -1);
v2 += x;
Change(v1, v2, +1);
FT.Update(l, r, x);
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
scanf("%d%d%d%d", &n, &q, &s, &t);
FOR(i, 0, n) scanf("%d", &a[i]);
FOR(i, 1, n)
if (a[i] > a[i - 1]) ans += (LL)s * (a[i - 1] - a[i]);
else ans += (LL)t * (a[i - 1] - a[i]);
while (q--) {
int l, r, x; scanf("%d%d%d", &l, &r, &x);
Update(l, r, x);
printf("%lld\n", ans);
}
return 0;
}
Compilation message
foehn_phenomena.cpp: In member function 'void FenwickTree::Update(int, int, int)':
foehn_phenomena.cpp:25:15: warning: statement has no effect [-Wunused-value]
for (l; l <= n; l += l & -l) fw[l] += v;
^
foehn_phenomena.cpp:27:15: warning: statement has no effect [-Wunused-value]
for (r; r <= n; r += r & -r) fw[r] -= v;
^
foehn_phenomena.cpp: In member function 'LL FenwickTree::Query(int)':
foehn_phenomena.cpp:31:15: warning: statement has no effect [-Wunused-value]
for (i; i > 0; i -= i & -i) ans += fw[i];
^
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:60:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &n, &q, &s, &t);
^
foehn_phenomena.cpp:61:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
FOR(i, 0, n) scanf("%d", &a[i]);
^
foehn_phenomena.cpp:66:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int l, r, x; scanf("%d%d%d", &l, &r, &x);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
4360 KB |
Output is correct |
2 |
Correct |
0 ms |
4360 KB |
Output is correct |
3 |
Correct |
0 ms |
4360 KB |
Output is correct |
4 |
Correct |
3 ms |
4360 KB |
Output is correct |
5 |
Correct |
0 ms |
4360 KB |
Output is correct |
6 |
Correct |
0 ms |
4360 KB |
Output is correct |
7 |
Correct |
3 ms |
4360 KB |
Output is correct |
8 |
Correct |
0 ms |
4360 KB |
Output is correct |
9 |
Correct |
0 ms |
4360 KB |
Output is correct |
10 |
Correct |
0 ms |
4360 KB |
Output is correct |
11 |
Correct |
0 ms |
4360 KB |
Output is correct |
12 |
Correct |
3 ms |
4360 KB |
Output is correct |
13 |
Correct |
0 ms |
4360 KB |
Output is correct |
14 |
Correct |
3 ms |
4360 KB |
Output is correct |
15 |
Correct |
0 ms |
4360 KB |
Output is correct |
16 |
Correct |
0 ms |
4360 KB |
Output is correct |
17 |
Correct |
0 ms |
4360 KB |
Output is correct |
18 |
Correct |
0 ms |
4360 KB |
Output is correct |
19 |
Correct |
0 ms |
4360 KB |
Output is correct |
20 |
Correct |
0 ms |
4360 KB |
Output is correct |
21 |
Correct |
0 ms |
4360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
193 ms |
4360 KB |
Output is correct |
2 |
Correct |
203 ms |
4360 KB |
Output is correct |
3 |
Correct |
206 ms |
4360 KB |
Output is correct |
4 |
Correct |
243 ms |
4360 KB |
Output is correct |
5 |
Correct |
256 ms |
4360 KB |
Output is correct |
6 |
Correct |
186 ms |
4360 KB |
Output is correct |
7 |
Correct |
149 ms |
4360 KB |
Output is correct |
8 |
Correct |
193 ms |
4360 KB |
Output is correct |
9 |
Correct |
219 ms |
4360 KB |
Output is correct |
10 |
Correct |
169 ms |
4360 KB |
Output is correct |
11 |
Correct |
133 ms |
4360 KB |
Output is correct |
12 |
Correct |
126 ms |
4360 KB |
Output is correct |
13 |
Correct |
139 ms |
4360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
4360 KB |
Output is correct |
2 |
Correct |
0 ms |
4360 KB |
Output is correct |
3 |
Correct |
0 ms |
4360 KB |
Output is correct |
4 |
Correct |
3 ms |
4360 KB |
Output is correct |
5 |
Correct |
0 ms |
4360 KB |
Output is correct |
6 |
Correct |
0 ms |
4360 KB |
Output is correct |
7 |
Correct |
3 ms |
4360 KB |
Output is correct |
8 |
Correct |
0 ms |
4360 KB |
Output is correct |
9 |
Correct |
0 ms |
4360 KB |
Output is correct |
10 |
Correct |
0 ms |
4360 KB |
Output is correct |
11 |
Correct |
0 ms |
4360 KB |
Output is correct |
12 |
Correct |
3 ms |
4360 KB |
Output is correct |
13 |
Correct |
0 ms |
4360 KB |
Output is correct |
14 |
Correct |
3 ms |
4360 KB |
Output is correct |
15 |
Correct |
0 ms |
4360 KB |
Output is correct |
16 |
Correct |
0 ms |
4360 KB |
Output is correct |
17 |
Correct |
0 ms |
4360 KB |
Output is correct |
18 |
Correct |
0 ms |
4360 KB |
Output is correct |
19 |
Correct |
0 ms |
4360 KB |
Output is correct |
20 |
Correct |
0 ms |
4360 KB |
Output is correct |
21 |
Correct |
0 ms |
4360 KB |
Output is correct |
22 |
Correct |
193 ms |
4360 KB |
Output is correct |
23 |
Correct |
203 ms |
4360 KB |
Output is correct |
24 |
Correct |
206 ms |
4360 KB |
Output is correct |
25 |
Correct |
243 ms |
4360 KB |
Output is correct |
26 |
Correct |
256 ms |
4360 KB |
Output is correct |
27 |
Correct |
186 ms |
4360 KB |
Output is correct |
28 |
Correct |
149 ms |
4360 KB |
Output is correct |
29 |
Correct |
193 ms |
4360 KB |
Output is correct |
30 |
Correct |
219 ms |
4360 KB |
Output is correct |
31 |
Correct |
169 ms |
4360 KB |
Output is correct |
32 |
Correct |
133 ms |
4360 KB |
Output is correct |
33 |
Correct |
126 ms |
4360 KB |
Output is correct |
34 |
Correct |
139 ms |
4360 KB |
Output is correct |
35 |
Correct |
183 ms |
4360 KB |
Output is correct |
36 |
Correct |
236 ms |
4360 KB |
Output is correct |
37 |
Correct |
213 ms |
4360 KB |
Output is correct |
38 |
Correct |
209 ms |
4360 KB |
Output is correct |
39 |
Correct |
199 ms |
4360 KB |
Output is correct |
40 |
Correct |
203 ms |
4360 KB |
Output is correct |
41 |
Correct |
216 ms |
4360 KB |
Output is correct |
42 |
Correct |
199 ms |
4360 KB |
Output is correct |
43 |
Correct |
203 ms |
4360 KB |
Output is correct |
44 |
Correct |
183 ms |
4360 KB |
Output is correct |
45 |
Correct |
209 ms |
4360 KB |
Output is correct |
46 |
Correct |
176 ms |
4360 KB |
Output is correct |
47 |
Correct |
133 ms |
4360 KB |
Output is correct |
48 |
Correct |
173 ms |
4360 KB |
Output is correct |
49 |
Correct |
173 ms |
4360 KB |
Output is correct |
50 |
Correct |
129 ms |
4360 KB |
Output is correct |
51 |
Correct |
159 ms |
4360 KB |
Output is correct |
52 |
Correct |
139 ms |
4360 KB |
Output is correct |