# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=3e5+5;
long long n,m,s,t,a[N],pr[N],le,ri,ad,prl,l,r,nxr,tree[2*N],tree2[2*N],xx,xx1;
void update1(long long idx, long long val) {
for (long long i=idx; i<=N; i+=i&(-i)) {
tree[i]+=val;
}
}
long long getans1(long long idx) {
long long pas=0;
for (long long i=idx; i>0; i-=i&(-i)) {
pas+=tree[i];
}
return pas;
}
void update2(long long idx, long long val) {
for (long long i=idx; i<=N; i+=i&(-i)) {
tree2[i]+=val;
}
}
long long getans2(long long idx) {
long long pas=0;
for (long long i=idx; i>0; i-=i&(-i)) {
pas+=tree2[i];
}
return pas;
}
long long go(long long a, long long b) {
if (a<b) return -abs(a-b)*s;
else return abs(a-b)*t;
}
int main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>s>>t;
for (int i=1; i<=n+1; i++) {
cin>>a[i];
update1(i,a[i]);
update1(i+1, -a[i]);
}
//cout<<getans1(1)<<endl<<endl;
pr[1]=0;
for (int i=2; i<=n+1; i++) {
long long ww=go(a[i-1],a[i]);
// cout<<i<<" "<<ww<<endl;
pr[i]=pr[i-1]+ww;
update2(i,ww);
// update2(i+1, -ww);
}
// cout<<getans2(n+1)<<endl<<endl<<endl;
for (int i=1; i<=m; i++) {
cin>>le>>ri>>ad;
le++;
ri++;
l=getans1(le);
prl=getans1(le-1);
xx=go(prl,l);
xx1=go(prl,l+ad);
//cout<<prl<<" "<<l<<" "<<xx<<" "<<xx1<<endl;
update2(le,xx1-xx);
//cout<<getans2(n+1)<<endl<<endl;
//update2(r+1, xx-xx1);
r=getans1(ri);
nxr=getans1(ri+1);
xx=go(r,nxr);
xx1=go(r+ad,nxr);//cout<<r<<" "<<nxr<<" "<<xx<<" "<<xx1<<endl;
update2(ri+1, xx1-xx);
cout<<getans2(n+1)<<endl;
update1(le,ad);
update1(ri+1, -ad);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
460 KB |
Output is correct |
2 |
Correct |
6 ms |
460 KB |
Output is correct |
3 |
Correct |
5 ms |
460 KB |
Output is correct |
4 |
Correct |
5 ms |
468 KB |
Output is correct |
5 |
Correct |
6 ms |
460 KB |
Output is correct |
6 |
Correct |
5 ms |
460 KB |
Output is correct |
7 |
Correct |
6 ms |
528 KB |
Output is correct |
8 |
Correct |
5 ms |
460 KB |
Output is correct |
9 |
Correct |
5 ms |
536 KB |
Output is correct |
10 |
Correct |
5 ms |
460 KB |
Output is correct |
11 |
Correct |
5 ms |
460 KB |
Output is correct |
12 |
Correct |
6 ms |
460 KB |
Output is correct |
13 |
Correct |
6 ms |
460 KB |
Output is correct |
14 |
Correct |
5 ms |
464 KB |
Output is correct |
15 |
Correct |
5 ms |
460 KB |
Output is correct |
16 |
Correct |
5 ms |
460 KB |
Output is correct |
17 |
Correct |
5 ms |
460 KB |
Output is correct |
18 |
Correct |
5 ms |
460 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
480 ms |
8004 KB |
Output is correct |
2 |
Correct |
492 ms |
8716 KB |
Output is correct |
3 |
Correct |
503 ms |
9236 KB |
Output is correct |
4 |
Correct |
492 ms |
14144 KB |
Output is correct |
5 |
Correct |
478 ms |
15172 KB |
Output is correct |
6 |
Correct |
455 ms |
14260 KB |
Output is correct |
7 |
Correct |
479 ms |
14284 KB |
Output is correct |
8 |
Correct |
492 ms |
15044 KB |
Output is correct |
9 |
Correct |
479 ms |
15424 KB |
Output is correct |
10 |
Correct |
504 ms |
14016 KB |
Output is correct |
11 |
Correct |
453 ms |
14180 KB |
Output is correct |
12 |
Correct |
458 ms |
14840 KB |
Output is correct |
13 |
Correct |
460 ms |
15092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
460 KB |
Output is correct |
2 |
Correct |
6 ms |
460 KB |
Output is correct |
3 |
Correct |
5 ms |
460 KB |
Output is correct |
4 |
Correct |
5 ms |
468 KB |
Output is correct |
5 |
Correct |
6 ms |
460 KB |
Output is correct |
6 |
Correct |
5 ms |
460 KB |
Output is correct |
7 |
Correct |
6 ms |
528 KB |
Output is correct |
8 |
Correct |
5 ms |
460 KB |
Output is correct |
9 |
Correct |
5 ms |
536 KB |
Output is correct |
10 |
Correct |
5 ms |
460 KB |
Output is correct |
11 |
Correct |
5 ms |
460 KB |
Output is correct |
12 |
Correct |
6 ms |
460 KB |
Output is correct |
13 |
Correct |
6 ms |
460 KB |
Output is correct |
14 |
Correct |
5 ms |
464 KB |
Output is correct |
15 |
Correct |
5 ms |
460 KB |
Output is correct |
16 |
Correct |
5 ms |
460 KB |
Output is correct |
17 |
Correct |
5 ms |
460 KB |
Output is correct |
18 |
Correct |
5 ms |
460 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
480 ms |
8004 KB |
Output is correct |
23 |
Correct |
492 ms |
8716 KB |
Output is correct |
24 |
Correct |
503 ms |
9236 KB |
Output is correct |
25 |
Correct |
492 ms |
14144 KB |
Output is correct |
26 |
Correct |
478 ms |
15172 KB |
Output is correct |
27 |
Correct |
455 ms |
14260 KB |
Output is correct |
28 |
Correct |
479 ms |
14284 KB |
Output is correct |
29 |
Correct |
492 ms |
15044 KB |
Output is correct |
30 |
Correct |
479 ms |
15424 KB |
Output is correct |
31 |
Correct |
504 ms |
14016 KB |
Output is correct |
32 |
Correct |
453 ms |
14180 KB |
Output is correct |
33 |
Correct |
458 ms |
14840 KB |
Output is correct |
34 |
Correct |
460 ms |
15092 KB |
Output is correct |
35 |
Correct |
494 ms |
13676 KB |
Output is correct |
36 |
Correct |
504 ms |
15196 KB |
Output is correct |
37 |
Correct |
491 ms |
15940 KB |
Output is correct |
38 |
Correct |
519 ms |
15684 KB |
Output is correct |
39 |
Correct |
507 ms |
15660 KB |
Output is correct |
40 |
Correct |
511 ms |
15648 KB |
Output is correct |
41 |
Correct |
495 ms |
15460 KB |
Output is correct |
42 |
Correct |
497 ms |
15584 KB |
Output is correct |
43 |
Correct |
509 ms |
14848 KB |
Output is correct |
44 |
Correct |
498 ms |
15208 KB |
Output is correct |
45 |
Correct |
484 ms |
15228 KB |
Output is correct |
46 |
Correct |
495 ms |
16284 KB |
Output is correct |
47 |
Correct |
458 ms |
14808 KB |
Output is correct |
48 |
Correct |
468 ms |
14864 KB |
Output is correct |
49 |
Correct |
477 ms |
13888 KB |
Output is correct |
50 |
Correct |
454 ms |
14752 KB |
Output is correct |
51 |
Correct |
454 ms |
15092 KB |
Output is correct |
52 |
Correct |
454 ms |
15004 KB |
Output is correct |