#include<bits/stdc++.h>
using namespace std;
int x, y, n, q;
long long z, s, t, a[200001], f[800001], tg[200001], lazy[800001], ans;
long long cal(int i)
{
return t*max(0ll,a[i-1]-a[i])-s*max(0ll,a[i]-a[i-1]);
}
void init(int k, int l, int r)
{
if(l>r)return;
if(l==r)
{
f[k]=a[l];
return;
}
int mid=(l+r)/2;
init(2*k,l,mid);
init(2*k+1,mid+1,r);
f[k]=max(f[2*k],f[2*k+1]);
}
void dolazy(int k, int l, int r)
{
if(lazy[k]==0)return;
f[k]+=lazy[k];
if(l!=r)
{
lazy[2*k]+=lazy[k];
lazy[2*k+1]+=lazy[k];
}
lazy[k]=0;
}
void upd(int k, int l, int r, int L, int R, long long x)
{
dolazy(k,l,r);
if(l>r||L>R||R<l||L>r)return;
if(L<=l&&r<=R)
{
f[k]+=x;
if(l!=r)
{
lazy[2*k]+=x;
lazy[2*k+1]+=x;
}
return;
}
int mid=(l+r)/2;
upd(2*k,l,mid,L,R,x);
upd(2*k+1,mid+1,r,L,R,x);
f[k]=max(f[2*k],f[2*k+1]);
}
long long gets(int k, int l, int r, int vt)
{
dolazy(k,l,r);
if(l>r||vt>r||vt<l)return 0ll;
if(l==r)return f[k];
int mid=(l+r)/2;
return gets(2*k,l,mid,vt)+gets(2*k+1,mid+1,r,vt);
}
int main()
{
scanf("%d%d%lld%lld",&n,&q,&s,&t);
for(int i=0;i<=n;++i)
{
scanf("%lld",&a[i]);
if(i>=1)
{
tg[i]=cal(i);
ans+=tg[i];
}
}
init(1,1,n);
while(q--)
{
scanf("%d%d%lld",&x,&y,&z);
upd(1,1,n,x,y,z);
a[x]=gets(1,1,n,x);
a[x-1]=gets(1,1,n,x-1);
ans+=cal(x)-tg[x];
tg[x]=cal(x);
if(y!=n)
{
a[y]=gets(1,1,n,y);
a[y+1]=gets(1,1,n,y+1);
ans+=cal(y+1)-tg[y+1];
tg[y+1]=cal(y+1);
}
printf("%lld\n",ans);
}
}
Compilation message
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:62:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld%lld",&n,&q,&s,&t);
^
foehn_phenomena.cpp:65:28: 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:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld",&x,&y,&z);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
17640 KB |
Output is correct |
2 |
Correct |
3 ms |
17640 KB |
Output is correct |
3 |
Correct |
0 ms |
17640 KB |
Output is correct |
4 |
Correct |
0 ms |
17640 KB |
Output is correct |
5 |
Correct |
3 ms |
17640 KB |
Output is correct |
6 |
Correct |
3 ms |
17640 KB |
Output is correct |
7 |
Correct |
0 ms |
17640 KB |
Output is correct |
8 |
Correct |
0 ms |
17640 KB |
Output is correct |
9 |
Correct |
3 ms |
17640 KB |
Output is correct |
10 |
Correct |
3 ms |
17640 KB |
Output is correct |
11 |
Correct |
3 ms |
17640 KB |
Output is correct |
12 |
Correct |
3 ms |
17640 KB |
Output is correct |
13 |
Correct |
0 ms |
17640 KB |
Output is correct |
14 |
Correct |
3 ms |
17640 KB |
Output is correct |
15 |
Correct |
3 ms |
17640 KB |
Output is correct |
16 |
Correct |
0 ms |
17640 KB |
Output is correct |
17 |
Correct |
0 ms |
17640 KB |
Output is correct |
18 |
Correct |
0 ms |
17640 KB |
Output is correct |
19 |
Correct |
0 ms |
17640 KB |
Output is correct |
20 |
Correct |
0 ms |
17640 KB |
Output is correct |
21 |
Correct |
0 ms |
17640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
836 ms |
17640 KB |
Output is correct |
2 |
Correct |
823 ms |
17640 KB |
Output is correct |
3 |
Correct |
846 ms |
17640 KB |
Output is correct |
4 |
Correct |
809 ms |
17640 KB |
Output is correct |
5 |
Correct |
883 ms |
17640 KB |
Output is correct |
6 |
Correct |
266 ms |
17640 KB |
Output is correct |
7 |
Correct |
273 ms |
17640 KB |
Output is correct |
8 |
Correct |
669 ms |
17640 KB |
Output is correct |
9 |
Correct |
736 ms |
17640 KB |
Output is correct |
10 |
Correct |
679 ms |
17640 KB |
Output is correct |
11 |
Correct |
329 ms |
17640 KB |
Output is correct |
12 |
Correct |
199 ms |
17640 KB |
Output is correct |
13 |
Correct |
279 ms |
17640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
17640 KB |
Output is correct |
2 |
Correct |
3 ms |
17640 KB |
Output is correct |
3 |
Correct |
0 ms |
17640 KB |
Output is correct |
4 |
Correct |
0 ms |
17640 KB |
Output is correct |
5 |
Correct |
3 ms |
17640 KB |
Output is correct |
6 |
Correct |
3 ms |
17640 KB |
Output is correct |
7 |
Correct |
0 ms |
17640 KB |
Output is correct |
8 |
Correct |
0 ms |
17640 KB |
Output is correct |
9 |
Correct |
3 ms |
17640 KB |
Output is correct |
10 |
Correct |
3 ms |
17640 KB |
Output is correct |
11 |
Correct |
3 ms |
17640 KB |
Output is correct |
12 |
Correct |
3 ms |
17640 KB |
Output is correct |
13 |
Correct |
0 ms |
17640 KB |
Output is correct |
14 |
Correct |
3 ms |
17640 KB |
Output is correct |
15 |
Correct |
3 ms |
17640 KB |
Output is correct |
16 |
Correct |
0 ms |
17640 KB |
Output is correct |
17 |
Correct |
0 ms |
17640 KB |
Output is correct |
18 |
Correct |
0 ms |
17640 KB |
Output is correct |
19 |
Correct |
0 ms |
17640 KB |
Output is correct |
20 |
Correct |
0 ms |
17640 KB |
Output is correct |
21 |
Correct |
0 ms |
17640 KB |
Output is correct |
22 |
Correct |
836 ms |
17640 KB |
Output is correct |
23 |
Correct |
823 ms |
17640 KB |
Output is correct |
24 |
Correct |
846 ms |
17640 KB |
Output is correct |
25 |
Correct |
809 ms |
17640 KB |
Output is correct |
26 |
Correct |
883 ms |
17640 KB |
Output is correct |
27 |
Correct |
266 ms |
17640 KB |
Output is correct |
28 |
Correct |
273 ms |
17640 KB |
Output is correct |
29 |
Correct |
669 ms |
17640 KB |
Output is correct |
30 |
Correct |
736 ms |
17640 KB |
Output is correct |
31 |
Correct |
679 ms |
17640 KB |
Output is correct |
32 |
Correct |
329 ms |
17640 KB |
Output is correct |
33 |
Correct |
199 ms |
17640 KB |
Output is correct |
34 |
Correct |
279 ms |
17640 KB |
Output is correct |
35 |
Correct |
779 ms |
17640 KB |
Output is correct |
36 |
Correct |
816 ms |
17640 KB |
Output is correct |
37 |
Correct |
823 ms |
17640 KB |
Output is correct |
38 |
Correct |
799 ms |
17640 KB |
Output is correct |
39 |
Correct |
793 ms |
17640 KB |
Output is correct |
40 |
Correct |
766 ms |
17640 KB |
Output is correct |
41 |
Correct |
783 ms |
17640 KB |
Output is correct |
42 |
Correct |
869 ms |
17640 KB |
Output is correct |
43 |
Correct |
706 ms |
17640 KB |
Output is correct |
44 |
Correct |
803 ms |
17640 KB |
Output is correct |
45 |
Correct |
803 ms |
17640 KB |
Output is correct |
46 |
Correct |
789 ms |
17640 KB |
Output is correct |
47 |
Correct |
219 ms |
17640 KB |
Output is correct |
48 |
Correct |
366 ms |
17640 KB |
Output is correct |
49 |
Correct |
806 ms |
17640 KB |
Output is correct |
50 |
Correct |
299 ms |
17640 KB |
Output is correct |
51 |
Correct |
226 ms |
17640 KB |
Output is correct |
52 |
Correct |
443 ms |
17640 KB |
Output is correct |