/* IN THE NAME OF GOD */
/* |\/| /-\ |\| | |\/| /-\ */
#include "bits/stdc++.h"
using namespace std;
#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define mr make_pair
//#define int long long
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;
mt19937 rng (chrono::high_resolution_clock::now().time_since_epoch().count());
const int N = 2e5 + 10;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 2e18;
ll seg[N * 4], lz[N * 4], ans;
int a[N];
void bulid(int id, int s, int e){
if(s == e){
seg[id] = a[s];
return;
}
int mid = (s + e) / 2;
bulid(id * 2, s, mid);
bulid(id * 2 + 1, mid + 1, e);
}
void shift(int id, int s, int e){
if(s == e)
return;
int mid = (s + e) / 2;
seg[id * 2] += lz[id] * (mid - s + 1);
seg[id * 2 + 1] += lz[id] * (e - mid);
lz[id * 2] += lz[id];
lz[id * 2 + 1] += lz[id];
lz[id] = 0;
}
void upd(int id, int s, int e, int l, int r, int x){
shift(id, s, e);
if(s > r || e < l)
return;
if(l <= s && e <= r){
seg[id] += (s - e + 1) * x;
lz[id] += x;
return;
}
int mid = (s + e) / 2;
upd(id * 2, s, mid, l, r, x);
upd(id * 2 + 1, mid + 1, e, l, r, x);
seg[id] = seg[id * 2] + seg[id * 2 + 1];
}
ll get(int id, int s, int e, int p){
shift(id, s, e);
if(s == e && s == p)
return seg[id];
if(s > p || e < p)
return 0;
int mid = (s + e) / 2;
return get(id * 2, s, mid, p) + get(id * 2 + 1, mid + 1, e, p);
}
int32_t main(){
ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, q;
ll s, t;
cin >> n >> q >> s >> t;
for(int i = 0; i <= n; i++)
cin >> a[i];
bulid(1, 1, n);
for(int i = 1; i <= n; i++){
if(a[i] > a[i - 1])
ans += -s * (a[i] - a[i - 1]);
else
ans += t * (a[i - 1] - a[i]);
}
int l, r, x;
while(q--){
cin >> l >> r >> x;
ll L = get(1, 1, n, l), Lm = get(1, 1, n, l - 1), R = get(1, 1, n, r), Rp = get(1, 1, n, r + 1);
//cout << Lm << " " << L << " " << R << " " << Rp << endl;
if(L > Lm)
ans -= -s * (L - Lm);
else
ans -= t * (Lm - L);
if(Rp > R && r != n)
ans -= -s * (Rp - R);
else if(r != n)
ans -= t * (R - Rp);
upd(1, 1, n, l, r, x);
L += x;
R += x;
if(L > Lm)
ans += -s * (L - Lm);
else
ans += t * (Lm - L);
if(Rp > R && r != n)
ans += -s * (Rp - R);
else if(r != n)
ans += t * (R - Rp);
cout << ans << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
468 KB |
Output is correct |
2 |
Correct |
5 ms |
468 KB |
Output is correct |
3 |
Correct |
3 ms |
508 KB |
Output is correct |
4 |
Correct |
3 ms |
476 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
3 ms |
488 KB |
Output is correct |
7 |
Correct |
3 ms |
476 KB |
Output is correct |
8 |
Correct |
4 ms |
468 KB |
Output is correct |
9 |
Correct |
4 ms |
476 KB |
Output is correct |
10 |
Correct |
4 ms |
468 KB |
Output is correct |
11 |
Correct |
3 ms |
468 KB |
Output is correct |
12 |
Correct |
4 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
416 KB |
Output is correct |
14 |
Correct |
3 ms |
468 KB |
Output is correct |
15 |
Correct |
3 ms |
468 KB |
Output is correct |
16 |
Correct |
3 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
388 KB |
Output is correct |
18 |
Correct |
3 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
434 ms |
10892 KB |
Output is correct |
2 |
Correct |
451 ms |
11808 KB |
Output is correct |
3 |
Correct |
453 ms |
12124 KB |
Output is correct |
4 |
Correct |
445 ms |
11356 KB |
Output is correct |
5 |
Correct |
447 ms |
12048 KB |
Output is correct |
6 |
Correct |
156 ms |
7328 KB |
Output is correct |
7 |
Correct |
155 ms |
7356 KB |
Output is correct |
8 |
Correct |
375 ms |
12476 KB |
Output is correct |
9 |
Correct |
372 ms |
12752 KB |
Output is correct |
10 |
Correct |
383 ms |
11700 KB |
Output is correct |
11 |
Correct |
300 ms |
7352 KB |
Output is correct |
12 |
Correct |
163 ms |
7884 KB |
Output is correct |
13 |
Correct |
255 ms |
8184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
468 KB |
Output is correct |
2 |
Correct |
5 ms |
468 KB |
Output is correct |
3 |
Correct |
3 ms |
508 KB |
Output is correct |
4 |
Correct |
3 ms |
476 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
3 ms |
488 KB |
Output is correct |
7 |
Correct |
3 ms |
476 KB |
Output is correct |
8 |
Correct |
4 ms |
468 KB |
Output is correct |
9 |
Correct |
4 ms |
476 KB |
Output is correct |
10 |
Correct |
4 ms |
468 KB |
Output is correct |
11 |
Correct |
3 ms |
468 KB |
Output is correct |
12 |
Correct |
4 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
416 KB |
Output is correct |
14 |
Correct |
3 ms |
468 KB |
Output is correct |
15 |
Correct |
3 ms |
468 KB |
Output is correct |
16 |
Correct |
3 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
388 KB |
Output is correct |
18 |
Correct |
3 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
434 ms |
10892 KB |
Output is correct |
23 |
Correct |
451 ms |
11808 KB |
Output is correct |
24 |
Correct |
453 ms |
12124 KB |
Output is correct |
25 |
Correct |
445 ms |
11356 KB |
Output is correct |
26 |
Correct |
447 ms |
12048 KB |
Output is correct |
27 |
Correct |
156 ms |
7328 KB |
Output is correct |
28 |
Correct |
155 ms |
7356 KB |
Output is correct |
29 |
Correct |
375 ms |
12476 KB |
Output is correct |
30 |
Correct |
372 ms |
12752 KB |
Output is correct |
31 |
Correct |
383 ms |
11700 KB |
Output is correct |
32 |
Correct |
300 ms |
7352 KB |
Output is correct |
33 |
Correct |
163 ms |
7884 KB |
Output is correct |
34 |
Correct |
255 ms |
8184 KB |
Output is correct |
35 |
Correct |
449 ms |
11140 KB |
Output is correct |
36 |
Correct |
506 ms |
12612 KB |
Output is correct |
37 |
Correct |
442 ms |
13376 KB |
Output is correct |
38 |
Correct |
449 ms |
13132 KB |
Output is correct |
39 |
Correct |
453 ms |
13132 KB |
Output is correct |
40 |
Correct |
449 ms |
13092 KB |
Output is correct |
41 |
Correct |
440 ms |
13004 KB |
Output is correct |
42 |
Correct |
450 ms |
13052 KB |
Output is correct |
43 |
Correct |
436 ms |
12364 KB |
Output is correct |
44 |
Correct |
438 ms |
12748 KB |
Output is correct |
45 |
Correct |
453 ms |
12504 KB |
Output is correct |
46 |
Correct |
445 ms |
13260 KB |
Output is correct |
47 |
Correct |
157 ms |
7976 KB |
Output is correct |
48 |
Correct |
276 ms |
8136 KB |
Output is correct |
49 |
Correct |
435 ms |
12216 KB |
Output is correct |
50 |
Correct |
311 ms |
7948 KB |
Output is correct |
51 |
Correct |
157 ms |
7904 KB |
Output is correct |
52 |
Correct |
341 ms |
7964 KB |
Output is correct |