#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio\
ios_base::sync_with_stdio(0);\
cin.tie(0);\
cout.tie(0)\
#define int long long
struct fenwickTree{
int n;
vi BIT;
fenwickTree(int sz){
n = sz;
BIT.resize(n + 1, 0);
}
void update(int i, int v){
if(i == 0) return;
while(i <= n){
BIT[i] += v;
i += i & (-i);
}
}
int query(int l, int r){
if(l > r) return 0;
if(l != 1) return query(1, r) - query(1, l - 1);
int res = 0;
while(r > 0){
res += BIT[r];
r -= r & (-r);
}
return res;
}
};
const int sz = 2e5 + 5;
int n, q, x, y, l, r, k, res, a[sz];
signed main(){
cin >> n >> q >> x >> y;
fenwickTree t(n + 1);
for(int i = 1; i <= n + 1; i++){
cin >> a[i];
t.update(i, a[i] - t.query(1, i - 1));
if(i > 1){
if(a[i] <= a[i - 1]) res += y * (a[i - 1] - a[i]);
else res -= x * (a[i] - a[i - 1]);
}
}
while(q--){
cin >> l >> r >> k;
l++, r++;
if(l > 1 and t.query(1, l) <= t.query(1, l - 1)) res -= y * abs(t.query(1, l) - t.query(1, l - 1));
else res += x * abs(t.query(1, l) - t.query(1, l - 1));
if(r < n + 1 and t.query(1, r + 1) < t.query(1, r)) res -= y * abs(t.query(1, r + 1) - t.query(1, r));
else res += x * abs(t.query(1, r + 1) - t.query(1, r));
t.update(l, k), t.update(r + 1, -k);
if(l > 1 and t.query(1, l) <= t.query(1, l - 1)) res += y * abs(t.query(1, l) - t.query(1, l - 1));
else res -= x * abs(t.query(1, l) - t.query(1, l - 1));
if(r < n + 1 and t.query(1, r + 1) <= t.query(1, r)) res += y * abs(t.query(1, r + 1) - t.query(1, r));
else res -= x * abs(t.query(1, r + 1) - t.query(1, r));
cout << res << endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
348 KB |
Output is correct |
2 |
Correct |
5 ms |
348 KB |
Output is correct |
3 |
Correct |
5 ms |
344 KB |
Output is correct |
4 |
Correct |
5 ms |
348 KB |
Output is correct |
5 |
Correct |
5 ms |
348 KB |
Output is correct |
6 |
Correct |
5 ms |
548 KB |
Output is correct |
7 |
Correct |
5 ms |
344 KB |
Output is correct |
8 |
Correct |
5 ms |
348 KB |
Output is correct |
9 |
Correct |
5 ms |
436 KB |
Output is correct |
10 |
Correct |
5 ms |
348 KB |
Output is correct |
11 |
Correct |
5 ms |
348 KB |
Output is correct |
12 |
Correct |
5 ms |
528 KB |
Output is correct |
13 |
Correct |
4 ms |
348 KB |
Output is correct |
14 |
Correct |
5 ms |
348 KB |
Output is correct |
15 |
Correct |
5 ms |
348 KB |
Output is correct |
16 |
Correct |
4 ms |
348 KB |
Output is correct |
17 |
Correct |
6 ms |
544 KB |
Output is correct |
18 |
Correct |
4 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
452 ms |
10324 KB |
Output is correct |
2 |
Correct |
470 ms |
10832 KB |
Output is correct |
3 |
Correct |
464 ms |
11812 KB |
Output is correct |
4 |
Correct |
446 ms |
10832 KB |
Output is correct |
5 |
Correct |
459 ms |
12112 KB |
Output is correct |
6 |
Correct |
412 ms |
11164 KB |
Output is correct |
7 |
Correct |
405 ms |
11092 KB |
Output is correct |
8 |
Incorrect |
447 ms |
11872 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
348 KB |
Output is correct |
2 |
Correct |
5 ms |
348 KB |
Output is correct |
3 |
Correct |
5 ms |
344 KB |
Output is correct |
4 |
Correct |
5 ms |
348 KB |
Output is correct |
5 |
Correct |
5 ms |
348 KB |
Output is correct |
6 |
Correct |
5 ms |
548 KB |
Output is correct |
7 |
Correct |
5 ms |
344 KB |
Output is correct |
8 |
Correct |
5 ms |
348 KB |
Output is correct |
9 |
Correct |
5 ms |
436 KB |
Output is correct |
10 |
Correct |
5 ms |
348 KB |
Output is correct |
11 |
Correct |
5 ms |
348 KB |
Output is correct |
12 |
Correct |
5 ms |
528 KB |
Output is correct |
13 |
Correct |
4 ms |
348 KB |
Output is correct |
14 |
Correct |
5 ms |
348 KB |
Output is correct |
15 |
Correct |
5 ms |
348 KB |
Output is correct |
16 |
Correct |
4 ms |
348 KB |
Output is correct |
17 |
Correct |
6 ms |
544 KB |
Output is correct |
18 |
Correct |
4 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
452 ms |
10324 KB |
Output is correct |
23 |
Correct |
470 ms |
10832 KB |
Output is correct |
24 |
Correct |
464 ms |
11812 KB |
Output is correct |
25 |
Correct |
446 ms |
10832 KB |
Output is correct |
26 |
Correct |
459 ms |
12112 KB |
Output is correct |
27 |
Correct |
412 ms |
11164 KB |
Output is correct |
28 |
Correct |
405 ms |
11092 KB |
Output is correct |
29 |
Incorrect |
447 ms |
11872 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |