#include <bits/stdc++.h>
using namespace std;
const int N = 200*1000+7;
long long a[N];
long long t[2][4*N];
long long T[4*N];
long long f[4*N];
inline void push(int v,int s,int e){
if(f[v]){
T[v] += ((e-s+1)*f[v]);
if(s!=e){
f[v*2] += f[v];
f[v*2+1] += f[v];
}
}
f[v] = 0;
}
inline void update(int v,int s,int e,int l,int r,long long val){
if(l>r) return;
push(v,s,e);
if(s == l && e == r){
f[v] += val;
return;
}
int m = (s+e)/2;
update(v*2,s,m,l,min(m,r),val);
update(v*2+1,m+1,e,max(l,m+1),r,val);
push(v*2,s,m);
push(v*2+1,m+1,e);
T[v] = T[v*2]+T[v*2+1];
}
inline long long query(int v,int s,int e,int l,int r){
if(l>r) return 0;
push(v,s,e);
if(s == l && e == r) return T[v];
int m = (s+e)/2;
return query(v*2,s,m,l,min(m,r))+query(v*2+1,m+1,e,max(l,m+1),r);
}
int n;
inline long long sum(int nshan,int r){
long long res = 0;
for (; r > 0; r = (r & (r+1)) - 1)
res += t[nshan][r];
return res;
}
inline long long query2(int nshan,int l,int r){
return sum(nshan,r)-sum(nshan,l-1);
}
inline long long update2(int nshan,int i,long long val){
long long dw = query2(nshan,i,i);
val-=dw;
for (; i <= n; i = (i | (i+1)))
t[nshan][i] += val;
}
int main(){
int q;
long long ss,tt;
scanf("%d%d%lld%lld",&n,&q,&ss,&tt);
for(int i = 0;i<=n;i++){
scanf("%lld",&a[i]);
update(1,0,n,i,i,a[i]);
}
for(int i = 1;i<=n;i++){
long long df = a[i-1]-a[i];
if(df>=0){
update2(1,i,df);
}
else{
update2(0,i,df);
}
}
while(q--){
int l,r;
long long val;
scanf("%d%d%lld",&l,&r,&val);
update2(0,l,0);
update2(1,l,0);
update(1,0,n,l,r,val);
long long x = query(1,0,n,l,l);
long long y = query(1,0,n,l-1,l-1);
y-=x;
if(y<0) {
update2(0,l,y);
}
else{
update2(1,l,y);
}
if(r<n){
update2(0,r+1,0);
update2(1,r+1,0);
x = query(1,0,n,r,r);
y = query(1,0,n,r+1,r+1);
x-=y;
if(x<0){
update2(0,r+1,x);
}
else{
update2(1,r+1,x);
}
}
long long w = query2(0,1,n);
w*=ss;
long long e = query2(1,1,n);
e*=tt;
w+=e;
printf("%lld\n",w);
}
return 0;
}
Compilation message
foehn_phenomena.cpp: In function 'long long int update2(int, int, long long int)':
foehn_phenomena.cpp:54:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld%lld",&n,&q,&ss,&tt);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&a[i]);
~~~~~^~~~~~~~~~~~~~
foehn_phenomena.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld",&l,&r,&val);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
504 KB |
Output is correct |
2 |
Correct |
8 ms |
676 KB |
Output is correct |
3 |
Correct |
8 ms |
776 KB |
Output is correct |
4 |
Correct |
7 ms |
776 KB |
Output is correct |
5 |
Correct |
7 ms |
948 KB |
Output is correct |
6 |
Correct |
7 ms |
960 KB |
Output is correct |
7 |
Correct |
8 ms |
1136 KB |
Output is correct |
8 |
Correct |
8 ms |
1148 KB |
Output is correct |
9 |
Correct |
7 ms |
1196 KB |
Output is correct |
10 |
Correct |
7 ms |
1260 KB |
Output is correct |
11 |
Correct |
7 ms |
1308 KB |
Output is correct |
12 |
Correct |
8 ms |
1360 KB |
Output is correct |
13 |
Correct |
6 ms |
1416 KB |
Output is correct |
14 |
Correct |
5 ms |
1460 KB |
Output is correct |
15 |
Correct |
7 ms |
1508 KB |
Output is correct |
16 |
Correct |
7 ms |
1676 KB |
Output is correct |
17 |
Correct |
5 ms |
1676 KB |
Output is correct |
18 |
Correct |
6 ms |
1676 KB |
Output is correct |
19 |
Correct |
2 ms |
1676 KB |
Output is correct |
20 |
Correct |
2 ms |
1676 KB |
Output is correct |
21 |
Correct |
2 ms |
1676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
913 ms |
20320 KB |
Output is correct |
2 |
Correct |
816 ms |
20832 KB |
Output is correct |
3 |
Correct |
882 ms |
21364 KB |
Output is correct |
4 |
Correct |
832 ms |
21364 KB |
Output is correct |
5 |
Correct |
871 ms |
21476 KB |
Output is correct |
6 |
Correct |
381 ms |
21824 KB |
Output is correct |
7 |
Correct |
382 ms |
21860 KB |
Output is correct |
8 |
Correct |
825 ms |
21892 KB |
Output is correct |
9 |
Correct |
699 ms |
22024 KB |
Output is correct |
10 |
Correct |
714 ms |
22024 KB |
Output is correct |
11 |
Correct |
484 ms |
22024 KB |
Output is correct |
12 |
Correct |
375 ms |
22024 KB |
Output is correct |
13 |
Correct |
400 ms |
22024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
504 KB |
Output is correct |
2 |
Correct |
8 ms |
676 KB |
Output is correct |
3 |
Correct |
8 ms |
776 KB |
Output is correct |
4 |
Correct |
7 ms |
776 KB |
Output is correct |
5 |
Correct |
7 ms |
948 KB |
Output is correct |
6 |
Correct |
7 ms |
960 KB |
Output is correct |
7 |
Correct |
8 ms |
1136 KB |
Output is correct |
8 |
Correct |
8 ms |
1148 KB |
Output is correct |
9 |
Correct |
7 ms |
1196 KB |
Output is correct |
10 |
Correct |
7 ms |
1260 KB |
Output is correct |
11 |
Correct |
7 ms |
1308 KB |
Output is correct |
12 |
Correct |
8 ms |
1360 KB |
Output is correct |
13 |
Correct |
6 ms |
1416 KB |
Output is correct |
14 |
Correct |
5 ms |
1460 KB |
Output is correct |
15 |
Correct |
7 ms |
1508 KB |
Output is correct |
16 |
Correct |
7 ms |
1676 KB |
Output is correct |
17 |
Correct |
5 ms |
1676 KB |
Output is correct |
18 |
Correct |
6 ms |
1676 KB |
Output is correct |
19 |
Correct |
2 ms |
1676 KB |
Output is correct |
20 |
Correct |
2 ms |
1676 KB |
Output is correct |
21 |
Correct |
2 ms |
1676 KB |
Output is correct |
22 |
Correct |
913 ms |
20320 KB |
Output is correct |
23 |
Correct |
816 ms |
20832 KB |
Output is correct |
24 |
Correct |
882 ms |
21364 KB |
Output is correct |
25 |
Correct |
832 ms |
21364 KB |
Output is correct |
26 |
Correct |
871 ms |
21476 KB |
Output is correct |
27 |
Correct |
381 ms |
21824 KB |
Output is correct |
28 |
Correct |
382 ms |
21860 KB |
Output is correct |
29 |
Correct |
825 ms |
21892 KB |
Output is correct |
30 |
Correct |
699 ms |
22024 KB |
Output is correct |
31 |
Correct |
714 ms |
22024 KB |
Output is correct |
32 |
Correct |
484 ms |
22024 KB |
Output is correct |
33 |
Correct |
375 ms |
22024 KB |
Output is correct |
34 |
Correct |
400 ms |
22024 KB |
Output is correct |
35 |
Correct |
892 ms |
22024 KB |
Output is correct |
36 |
Correct |
930 ms |
22024 KB |
Output is correct |
37 |
Correct |
875 ms |
22824 KB |
Output is correct |
38 |
Correct |
884 ms |
22824 KB |
Output is correct |
39 |
Correct |
905 ms |
22824 KB |
Output is correct |
40 |
Correct |
863 ms |
22824 KB |
Output is correct |
41 |
Correct |
851 ms |
22824 KB |
Output is correct |
42 |
Correct |
917 ms |
22824 KB |
Output is correct |
43 |
Correct |
877 ms |
22824 KB |
Output is correct |
44 |
Correct |
900 ms |
22824 KB |
Output is correct |
45 |
Correct |
909 ms |
22824 KB |
Output is correct |
46 |
Correct |
837 ms |
22824 KB |
Output is correct |
47 |
Correct |
444 ms |
22824 KB |
Output is correct |
48 |
Correct |
449 ms |
22824 KB |
Output is correct |
49 |
Correct |
852 ms |
22824 KB |
Output is correct |
50 |
Correct |
433 ms |
22824 KB |
Output is correct |
51 |
Correct |
398 ms |
22824 KB |
Output is correct |
52 |
Correct |
503 ms |
22824 KB |
Output is correct |