#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define AI(x) begin(x),end(x)
#define endl '\n'
struct BIT{
vector<long long> arr;
int n;
void init(int _n) {
n = _n;
arr.resize(n+5);
}
long long query(int i) {
long long sum = 0;
for (i; i > 0; i -= (i&-i)) {
sum += arr[i];
}
return sum;
}
void modify(int i, long long v) {
for (i; i <= n; i += (i&-i)) {
arr[i] += v;
}
}
};
signed main() {
long long n, q, s, t;
cin >> n >> q >> s >> t;
s = -s;
t = -t;
vector<long long> arr(n+1);
for (auto &i : arr) cin >> i;
vector<long long> diff(n+1);
for (int i = 1; i <= n; ++i) {
if (arr[i] > arr[i-1]) {
diff[i] = s * (arr[i] - arr[i-1]);
}
else {
diff[i] = t * (arr[i] - arr[i-1]);
}
}
BIT bit, h;
bit.init(n+1);
h.init(n+1);
for (int i = 1; i <= n; ++i) {
bit.modify(i, diff[i]);
h.modify(i, arr[i] - arr[i-1]);
}
// for (int i = 0; i <= n; ++i) cerr << h.query(i) << " "; cerr << endl;
// for (int i = 0; i <= n; ++i) cerr << bit.query(i) << " "; cerr << endl;
while(q--) {
long long l, r, x;
cin >> l >> r >> x;
long long ll = bit.query(l) - bit.query(l-1);
long long rr = bit.query(r+1) - bit.query(r);
long long lh = h.query(l) - h.query(l-1);
long long lhn = lh + x;
if (lhn > 0) bit.modify(l, lhn*s - ll);
else bit.modify(l, lhn*t - ll);
long long rh = h.query(r+1) - h.query(r);
long long rhn = rh - x;
if (rhn > 0) bit.modify(r+1, rhn*s - rr);
else bit.modify(r+1, rhn*t - rr);
h.modify(l, x);
h.modify(r+1, -x);
// cerr << "H: "; for (int i = 0; i <= n; ++i) cerr << h.query(i) << " "; cerr << endl;
// cerr << "T: "; for (int i = 0; i <= n; ++i) cerr << bit.query(i) << " "; cerr << endl;
cout << bit.query(n) << endl;
}
}
Compilation message
foehn_phenomena.cpp: In member function 'long long int BIT::query(int)':
foehn_phenomena.cpp:17:8: warning: statement has no effect [-Wunused-value]
17 | for (i; i > 0; i -= (i&-i)) {
| ^
foehn_phenomena.cpp: In member function 'void BIT::modify(int, long long int)':
foehn_phenomena.cpp:24:8: warning: statement has no effect [-Wunused-value]
24 | for (i; i <= n; i += (i&-i)) {
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
348 KB |
Output is correct |
2 |
Correct |
5 ms |
348 KB |
Output is correct |
3 |
Correct |
5 ms |
348 KB |
Output is correct |
4 |
Correct |
5 ms |
348 KB |
Output is correct |
5 |
Correct |
5 ms |
448 KB |
Output is correct |
6 |
Correct |
5 ms |
348 KB |
Output is correct |
7 |
Correct |
5 ms |
348 KB |
Output is correct |
8 |
Correct |
5 ms |
348 KB |
Output is correct |
9 |
Correct |
5 ms |
348 KB |
Output is correct |
10 |
Correct |
4 ms |
348 KB |
Output is correct |
11 |
Correct |
5 ms |
344 KB |
Output is correct |
12 |
Correct |
5 ms |
448 KB |
Output is correct |
13 |
Correct |
5 ms |
348 KB |
Output is correct |
14 |
Correct |
4 ms |
520 KB |
Output is correct |
15 |
Correct |
4 ms |
348 KB |
Output is correct |
16 |
Correct |
4 ms |
348 KB |
Output is correct |
17 |
Correct |
5 ms |
348 KB |
Output is correct |
18 |
Correct |
4 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
473 ms |
8420 KB |
Output is correct |
2 |
Correct |
494 ms |
8676 KB |
Output is correct |
3 |
Correct |
471 ms |
9300 KB |
Output is correct |
4 |
Correct |
478 ms |
8292 KB |
Output is correct |
5 |
Correct |
471 ms |
9176 KB |
Output is correct |
6 |
Correct |
432 ms |
9672 KB |
Output is correct |
7 |
Correct |
436 ms |
9836 KB |
Output is correct |
8 |
Correct |
465 ms |
9540 KB |
Output is correct |
9 |
Correct |
526 ms |
9844 KB |
Output is correct |
10 |
Correct |
463 ms |
8528 KB |
Output is correct |
11 |
Correct |
421 ms |
9552 KB |
Output is correct |
12 |
Correct |
449 ms |
9852 KB |
Output is correct |
13 |
Correct |
433 ms |
10580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
348 KB |
Output is correct |
2 |
Correct |
5 ms |
348 KB |
Output is correct |
3 |
Correct |
5 ms |
348 KB |
Output is correct |
4 |
Correct |
5 ms |
348 KB |
Output is correct |
5 |
Correct |
5 ms |
448 KB |
Output is correct |
6 |
Correct |
5 ms |
348 KB |
Output is correct |
7 |
Correct |
5 ms |
348 KB |
Output is correct |
8 |
Correct |
5 ms |
348 KB |
Output is correct |
9 |
Correct |
5 ms |
348 KB |
Output is correct |
10 |
Correct |
4 ms |
348 KB |
Output is correct |
11 |
Correct |
5 ms |
344 KB |
Output is correct |
12 |
Correct |
5 ms |
448 KB |
Output is correct |
13 |
Correct |
5 ms |
348 KB |
Output is correct |
14 |
Correct |
4 ms |
520 KB |
Output is correct |
15 |
Correct |
4 ms |
348 KB |
Output is correct |
16 |
Correct |
4 ms |
348 KB |
Output is correct |
17 |
Correct |
5 ms |
348 KB |
Output is correct |
18 |
Correct |
4 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
473 ms |
8420 KB |
Output is correct |
23 |
Correct |
494 ms |
8676 KB |
Output is correct |
24 |
Correct |
471 ms |
9300 KB |
Output is correct |
25 |
Correct |
478 ms |
8292 KB |
Output is correct |
26 |
Correct |
471 ms |
9176 KB |
Output is correct |
27 |
Correct |
432 ms |
9672 KB |
Output is correct |
28 |
Correct |
436 ms |
9836 KB |
Output is correct |
29 |
Correct |
465 ms |
9540 KB |
Output is correct |
30 |
Correct |
526 ms |
9844 KB |
Output is correct |
31 |
Correct |
463 ms |
8528 KB |
Output is correct |
32 |
Correct |
421 ms |
9552 KB |
Output is correct |
33 |
Correct |
449 ms |
9852 KB |
Output is correct |
34 |
Correct |
433 ms |
10580 KB |
Output is correct |
35 |
Correct |
461 ms |
8276 KB |
Output is correct |
36 |
Correct |
482 ms |
9556 KB |
Output is correct |
37 |
Correct |
474 ms |
10532 KB |
Output is correct |
38 |
Correct |
471 ms |
10068 KB |
Output is correct |
39 |
Correct |
490 ms |
10176 KB |
Output is correct |
40 |
Correct |
490 ms |
10172 KB |
Output is correct |
41 |
Correct |
475 ms |
10068 KB |
Output is correct |
42 |
Correct |
492 ms |
10068 KB |
Output is correct |
43 |
Correct |
472 ms |
9300 KB |
Output is correct |
44 |
Correct |
464 ms |
9808 KB |
Output is correct |
45 |
Correct |
464 ms |
9676 KB |
Output is correct |
46 |
Correct |
478 ms |
10436 KB |
Output is correct |
47 |
Correct |
430 ms |
10328 KB |
Output is correct |
48 |
Correct |
441 ms |
10604 KB |
Output is correct |
49 |
Correct |
444 ms |
9508 KB |
Output is correct |
50 |
Correct |
421 ms |
10504 KB |
Output is correct |
51 |
Correct |
443 ms |
10068 KB |
Output is correct |
52 |
Correct |
432 ms |
10128 KB |
Output is correct |