#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
struct segtree{
int t[4*N];
int query(int v,int tl,int tr,int l,int r){
if(tl>r||tr<l)return 0;
if(tl >= l &&tr<=r)return t[v];
int tm=(tl+tr)/2;
return query(v*2,tl,tm,l,r)+query(v*2+1,tm+1,tr,l,r);
}
void update(int v,int tl,int tr,int index,int value){
if(tl==tr)t[v]=value;
else {
int tm=(tl+tr)/2;
if(index<=tm)update(v*2,tl,tm,index,value);
else update(v*2+1,tm+1,tr,index,value);
t[v]=t[v*2]+t[v*2+1];
}
}
void update(int i, int v) {
update(1, 0, N, i, v);
}
int query(int l, int r) {
return query(1, 0, N, l, r);
}
}seg1, seg2;
struct fenw {
int t[N];
int query(int i) {
i += 1;
int ans = 0;
while(i) {
ans += t[i];
i -= i & - i;
}
return ans;
}
void update(int i, int v) {
i += 1;
while(i < N) {
t[i] += v;
i += i & - i;
}
}
}fenw;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q, s, t;
cin >> n >> q >> s >> t;
vector<int> a(n + 1);
for(int i = 0; i <= n; i++) {
cin >> a[i];
}
for(int i = 0; i < n; i++) {
if(a[i] < a[i + 1]) {
seg1.update(i, a[i + 1] - a[i]);
seg2.update(i, 0);
}
else {
seg2.update(i, a[i] - a[i + 1]);
seg1.update(i, 0);
}
}
for(int i = 0; i <= n; i++) {
fenw.update(i, a[i]);
fenw.update(i + 1, - a[i]);
}
while(q--) {
int l, r, x;
cin >> l >> r >> x;
fenw.update(l, x);
fenw.update(r + 1, - x);
/**
for(int i = l; i <= r; i++) {
a[i] += x;
}
int u1 = 0;
int u2 = 0;
for(int i = 0; i < n; i++) {
if(a[i] < a[i + 1]) {
//u -= s * (a[i + 1] - a[i]);
u1 += a[i + 1] - a[i];
}
else {
//u += t * (a[i] - a[i + 1]);
u2 += a[i] - a[i + 1];
}
}
cout << u2 * t << " " << u1 * s << "\n";**/
if(l) {
int idx = fenw.query(l - 1);
int in = fenw.query(l);
if(idx < in) {
seg1.update(l - 1, in - idx);
seg2.update(l - 1, 0);
}
else {
seg1.update(l - 1, 0);
seg2.update(l - 1, idx - in);
}
}
if(l + 1 <= n) {
int idx = fenw.query(l);
int in = fenw.query(l + 1);
if(idx < in) {
seg1.update(l, in - idx);
seg2.update(l, 0);
}
else {
seg1.update(l, 0);
seg2.update(l, idx - in);
}
}
if(r) {
int idx = fenw.query(r - 1);
int in = fenw.query(r);
if(idx < in) {
seg1.update(r - 1, in - idx);
seg2.update(r - 1, 0);
}
else {
seg1.update(r - 1, 0);
seg2.update(r - 1, idx - in);
}
}
if(r + 1 <= n) {
int idx = fenw.query(r);
int in = fenw.query(r + 1);
if(idx < in) {
seg1.update(r, in - idx);
seg2.update(r, 0);
}
else {
seg1.update(r, 0);
seg2.update(r, idx - in);
}
}
cout << seg2.query(0, n - 1) * t - seg1.query(0, n - 1) * s << "\n";
}
//cout << fenw2.query(n) * t - fenw1.query(n) * s;
}
/*
mogu izvucem s i t pre zagrade
jedino sto se menja jeste razlika izmedju r i r + 1 i l i l - 1
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
8540 KB |
Output is correct |
2 |
Correct |
4 ms |
8540 KB |
Output is correct |
3 |
Correct |
5 ms |
8540 KB |
Output is correct |
4 |
Correct |
4 ms |
8540 KB |
Output is correct |
5 |
Correct |
5 ms |
8540 KB |
Output is correct |
6 |
Correct |
4 ms |
8540 KB |
Output is correct |
7 |
Correct |
5 ms |
8540 KB |
Output is correct |
8 |
Correct |
5 ms |
8540 KB |
Output is correct |
9 |
Correct |
4 ms |
8540 KB |
Output is correct |
10 |
Correct |
4 ms |
8540 KB |
Output is correct |
11 |
Correct |
4 ms |
8536 KB |
Output is correct |
12 |
Correct |
6 ms |
8540 KB |
Output is correct |
13 |
Correct |
3 ms |
8536 KB |
Output is correct |
14 |
Correct |
4 ms |
8540 KB |
Output is correct |
15 |
Correct |
4 ms |
8536 KB |
Output is correct |
16 |
Correct |
4 ms |
8540 KB |
Output is correct |
17 |
Correct |
3 ms |
8540 KB |
Output is correct |
18 |
Correct |
3 ms |
8540 KB |
Output is correct |
19 |
Correct |
2 ms |
8540 KB |
Output is correct |
20 |
Correct |
2 ms |
8540 KB |
Output is correct |
21 |
Correct |
2 ms |
8540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
352 ms |
19520 KB |
Output is correct |
2 |
Correct |
389 ms |
21840 KB |
Output is correct |
3 |
Correct |
322 ms |
22788 KB |
Output is correct |
4 |
Correct |
310 ms |
21744 KB |
Output is correct |
5 |
Correct |
343 ms |
23024 KB |
Output is correct |
6 |
Correct |
174 ms |
21908 KB |
Output is correct |
7 |
Correct |
186 ms |
22096 KB |
Output is correct |
8 |
Correct |
311 ms |
22868 KB |
Output is correct |
9 |
Correct |
315 ms |
23164 KB |
Output is correct |
10 |
Correct |
305 ms |
21864 KB |
Output is correct |
11 |
Correct |
204 ms |
21852 KB |
Output is correct |
12 |
Correct |
172 ms |
22612 KB |
Output is correct |
13 |
Correct |
184 ms |
22776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
8540 KB |
Output is correct |
2 |
Correct |
4 ms |
8540 KB |
Output is correct |
3 |
Correct |
5 ms |
8540 KB |
Output is correct |
4 |
Correct |
4 ms |
8540 KB |
Output is correct |
5 |
Correct |
5 ms |
8540 KB |
Output is correct |
6 |
Correct |
4 ms |
8540 KB |
Output is correct |
7 |
Correct |
5 ms |
8540 KB |
Output is correct |
8 |
Correct |
5 ms |
8540 KB |
Output is correct |
9 |
Correct |
4 ms |
8540 KB |
Output is correct |
10 |
Correct |
4 ms |
8540 KB |
Output is correct |
11 |
Correct |
4 ms |
8536 KB |
Output is correct |
12 |
Correct |
6 ms |
8540 KB |
Output is correct |
13 |
Correct |
3 ms |
8536 KB |
Output is correct |
14 |
Correct |
4 ms |
8540 KB |
Output is correct |
15 |
Correct |
4 ms |
8536 KB |
Output is correct |
16 |
Correct |
4 ms |
8540 KB |
Output is correct |
17 |
Correct |
3 ms |
8540 KB |
Output is correct |
18 |
Correct |
3 ms |
8540 KB |
Output is correct |
19 |
Correct |
2 ms |
8540 KB |
Output is correct |
20 |
Correct |
2 ms |
8540 KB |
Output is correct |
21 |
Correct |
2 ms |
8540 KB |
Output is correct |
22 |
Correct |
352 ms |
19520 KB |
Output is correct |
23 |
Correct |
389 ms |
21840 KB |
Output is correct |
24 |
Correct |
322 ms |
22788 KB |
Output is correct |
25 |
Correct |
310 ms |
21744 KB |
Output is correct |
26 |
Correct |
343 ms |
23024 KB |
Output is correct |
27 |
Correct |
174 ms |
21908 KB |
Output is correct |
28 |
Correct |
186 ms |
22096 KB |
Output is correct |
29 |
Correct |
311 ms |
22868 KB |
Output is correct |
30 |
Correct |
315 ms |
23164 KB |
Output is correct |
31 |
Correct |
305 ms |
21864 KB |
Output is correct |
32 |
Correct |
204 ms |
21852 KB |
Output is correct |
33 |
Correct |
172 ms |
22612 KB |
Output is correct |
34 |
Correct |
184 ms |
22776 KB |
Output is correct |
35 |
Correct |
324 ms |
21328 KB |
Output is correct |
36 |
Correct |
354 ms |
22968 KB |
Output is correct |
37 |
Correct |
409 ms |
23648 KB |
Output is correct |
38 |
Correct |
327 ms |
23376 KB |
Output is correct |
39 |
Correct |
368 ms |
23788 KB |
Output is correct |
40 |
Correct |
389 ms |
23420 KB |
Output is correct |
41 |
Correct |
344 ms |
23120 KB |
Output is correct |
42 |
Correct |
391 ms |
23632 KB |
Output is correct |
43 |
Correct |
345 ms |
22608 KB |
Output is correct |
44 |
Correct |
338 ms |
23148 KB |
Output is correct |
45 |
Correct |
338 ms |
23112 KB |
Output is correct |
46 |
Correct |
408 ms |
24172 KB |
Output is correct |
47 |
Correct |
183 ms |
22628 KB |
Output is correct |
48 |
Correct |
190 ms |
22644 KB |
Output is correct |
49 |
Correct |
331 ms |
21780 KB |
Output is correct |
50 |
Correct |
189 ms |
22732 KB |
Output is correct |
51 |
Correct |
191 ms |
22764 KB |
Output is correct |
52 |
Correct |
197 ms |
22612 KB |
Output is correct |