#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=2*1e5+7;
vector<ll> bit1(MAX,0);
vector<ll> bit2(MAX,0);
vector<ll> incr(MAX,0);
vector<ll> decr(MAX,0);
ll n;
void upd1(int pos, ll val) {
while (pos<=n) {
bit1[pos]+=val;
pos+=pos&-pos;
}
}
void upd2(int pos, ll val) {
while (pos<=n) {
bit2[pos]+=val;
pos+=pos&-pos;
}
}
ll query1(int pos) {
ll ans=0;
while (pos>0) {
ans+=bit1[pos];
pos-=pos&-pos;
}
return ans;
}
ll query2(int pos) {
ll ans=0;
while (pos>0) {
ans+=bit2[pos];
pos-=pos&-pos;
}
return ans;
}
int main() {
ll q,s,t; cin>>n>>q>>s>>t;
vector<ll> a(n+1);
for (int i=0; i<=n; i++) cin>>a[i];
for (int i=1; i<=n; i++) {
if (a[i]>a[i-1]) {
incr[i]=a[i]-a[i-1];
upd1(i,incr[i]);
}
else {
decr[i]=a[i-1]-a[i];
upd2(i,decr[i]);
}
}
while (q--) {
ll l,r,x; cin>>l>>r>>x;
if (incr[l]!=0) {
if (incr[l]+x>=0) {
upd1(l,x);
incr[l]+=x;
}
else {
upd2(l,-x-incr[l]);
decr[l]+=-x-incr[l];
upd1(l,-incr[l]);
incr[l]+=-incr[l];
}
} else {
x=-x;
if (decr[l]+x>=0) {
upd2(l,x);
decr[l]+=x;
}
else {
upd1(l,-x-decr[l]);
incr[l]+=-x-decr[l];
upd2(l,-decr[l]);
decr[l]+=-decr[l];
}
x=-x;
}
if (r<n) {
x=-x;
l=r+1;
if (incr[l]!=0) {
if (incr[l]+x>=0) {
upd1(l,x);
incr[l]+=x;
}
else {
upd2(l,-x-incr[l]);
decr[l]+=-x-incr[l];
upd1(l,-incr[l]);
incr[l]+=-incr[l];
}
} else {
x=-x;
if (decr[l]+x>=0) {
upd2(l,x);
decr[l]+=x;
}
else {
upd1(l,-x-decr[l]);
incr[l]+=-x-decr[l];
upd2(l,-decr[l]);
decr[l]+=-decr[l];
}
x=-x;
}
}
cout<<t*query2(n)-s*query1(n)<<"\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
6736 KB |
Output is correct |
2 |
Correct |
7 ms |
6748 KB |
Output is correct |
3 |
Correct |
6 ms |
6748 KB |
Output is correct |
4 |
Correct |
7 ms |
6748 KB |
Output is correct |
5 |
Correct |
7 ms |
6748 KB |
Output is correct |
6 |
Correct |
7 ms |
6748 KB |
Output is correct |
7 |
Correct |
7 ms |
6748 KB |
Output is correct |
8 |
Correct |
7 ms |
6748 KB |
Output is correct |
9 |
Correct |
7 ms |
6744 KB |
Output is correct |
10 |
Correct |
7 ms |
6744 KB |
Output is correct |
11 |
Correct |
7 ms |
6748 KB |
Output is correct |
12 |
Correct |
7 ms |
6744 KB |
Output is correct |
13 |
Correct |
6 ms |
6748 KB |
Output is correct |
14 |
Correct |
7 ms |
6744 KB |
Output is correct |
15 |
Correct |
6 ms |
6748 KB |
Output is correct |
16 |
Correct |
7 ms |
6748 KB |
Output is correct |
17 |
Correct |
7 ms |
6748 KB |
Output is correct |
18 |
Correct |
8 ms |
6744 KB |
Output is correct |
19 |
Correct |
3 ms |
6492 KB |
Output is correct |
20 |
Correct |
3 ms |
6492 KB |
Output is correct |
21 |
Correct |
3 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
457 ms |
9820 KB |
Output is correct |
2 |
Correct |
469 ms |
10320 KB |
Output is correct |
3 |
Correct |
475 ms |
10836 KB |
Output is correct |
4 |
Correct |
454 ms |
10060 KB |
Output is correct |
5 |
Correct |
465 ms |
10812 KB |
Output is correct |
6 |
Correct |
443 ms |
11084 KB |
Output is correct |
7 |
Correct |
440 ms |
11156 KB |
Output is correct |
8 |
Correct |
475 ms |
11064 KB |
Output is correct |
9 |
Correct |
445 ms |
11584 KB |
Output is correct |
10 |
Correct |
448 ms |
10336 KB |
Output is correct |
11 |
Correct |
437 ms |
11116 KB |
Output is correct |
12 |
Correct |
428 ms |
11592 KB |
Output is correct |
13 |
Correct |
417 ms |
12116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
6736 KB |
Output is correct |
2 |
Correct |
7 ms |
6748 KB |
Output is correct |
3 |
Correct |
6 ms |
6748 KB |
Output is correct |
4 |
Correct |
7 ms |
6748 KB |
Output is correct |
5 |
Correct |
7 ms |
6748 KB |
Output is correct |
6 |
Correct |
7 ms |
6748 KB |
Output is correct |
7 |
Correct |
7 ms |
6748 KB |
Output is correct |
8 |
Correct |
7 ms |
6748 KB |
Output is correct |
9 |
Correct |
7 ms |
6744 KB |
Output is correct |
10 |
Correct |
7 ms |
6744 KB |
Output is correct |
11 |
Correct |
7 ms |
6748 KB |
Output is correct |
12 |
Correct |
7 ms |
6744 KB |
Output is correct |
13 |
Correct |
6 ms |
6748 KB |
Output is correct |
14 |
Correct |
7 ms |
6744 KB |
Output is correct |
15 |
Correct |
6 ms |
6748 KB |
Output is correct |
16 |
Correct |
7 ms |
6748 KB |
Output is correct |
17 |
Correct |
7 ms |
6748 KB |
Output is correct |
18 |
Correct |
8 ms |
6744 KB |
Output is correct |
19 |
Correct |
3 ms |
6492 KB |
Output is correct |
20 |
Correct |
3 ms |
6492 KB |
Output is correct |
21 |
Correct |
3 ms |
6492 KB |
Output is correct |
22 |
Correct |
457 ms |
9820 KB |
Output is correct |
23 |
Correct |
469 ms |
10320 KB |
Output is correct |
24 |
Correct |
475 ms |
10836 KB |
Output is correct |
25 |
Correct |
454 ms |
10060 KB |
Output is correct |
26 |
Correct |
465 ms |
10812 KB |
Output is correct |
27 |
Correct |
443 ms |
11084 KB |
Output is correct |
28 |
Correct |
440 ms |
11156 KB |
Output is correct |
29 |
Correct |
475 ms |
11064 KB |
Output is correct |
30 |
Correct |
445 ms |
11584 KB |
Output is correct |
31 |
Correct |
448 ms |
10336 KB |
Output is correct |
32 |
Correct |
437 ms |
11116 KB |
Output is correct |
33 |
Correct |
428 ms |
11592 KB |
Output is correct |
34 |
Correct |
417 ms |
12116 KB |
Output is correct |
35 |
Correct |
478 ms |
15024 KB |
Output is correct |
36 |
Correct |
447 ms |
16780 KB |
Output is correct |
37 |
Correct |
450 ms |
17492 KB |
Output is correct |
38 |
Correct |
450 ms |
17240 KB |
Output is correct |
39 |
Correct |
490 ms |
17104 KB |
Output is correct |
40 |
Correct |
455 ms |
17488 KB |
Output is correct |
41 |
Correct |
456 ms |
17084 KB |
Output is correct |
42 |
Correct |
439 ms |
16976 KB |
Output is correct |
43 |
Correct |
517 ms |
16716 KB |
Output is correct |
44 |
Correct |
487 ms |
16784 KB |
Output is correct |
45 |
Correct |
469 ms |
16888 KB |
Output is correct |
46 |
Correct |
473 ms |
17744 KB |
Output is correct |
47 |
Correct |
425 ms |
16604 KB |
Output is correct |
48 |
Correct |
421 ms |
16728 KB |
Output is correct |
49 |
Correct |
443 ms |
15444 KB |
Output is correct |
50 |
Correct |
420 ms |
16368 KB |
Output is correct |
51 |
Correct |
418 ms |
16724 KB |
Output is correct |
52 |
Correct |
415 ms |
16408 KB |
Output is correct |