#include <bits/stdc++.h>
using namespace std;
int64_t n,T,s,t,res=0,a[200005],tree[200005];
void Update(int64_t idx,int64_t data)
{
while(idx<=n)
{
tree[idx]+=data;
idx+=idx&-idx;
}
}
int64_t Query(int64_t idx)
{
int64_t rs=0;
while(idx>0)
{
rs+=tree[idx];
idx-=idx&-idx;
}
return rs;
}
void Updateres(int64_t l,int64_t r,int64_t type)
{
int64_t t1,t2;
if(l==1)
t1=0;
else
t1=Query(l-1);
t2=Query(l);
if(t1<t2)
res-=s*(t2-t1)*type;
else
res+=t*(t1-t2)*type;
if(r<n)
{
t1=Query(r);
t2=Query(r+1);
if(t1<t2)
res-=s*(t2-t1)*type;
else
res+=t*(t1-t2)*type;
}
}
int main()
{
ios_base::sync_with_stdio(false);
//freopen("TEST.INP","r",stdin);
cin>>n>>T>>s>>t;
for(int64_t i=0; i<=n; i++)
{
cin>>a[i];
if(i>0)
{
Update(i,a[i]);
Update(i+1,-a[i]);
}
}
for(int64_t i=1; i<=n; i++)
if(a[i-1]<a[i])
res-=s*(a[i]-a[i-1]);
else
res+=t*(a[i-1]-a[i]);
int64_t l,r,val;
while(T--)
{
cin>>l>>r>>val;
Updateres(l,r,-1);
Update(l,val);
Update(r+1,-val);
Updateres(l,r,1);
cout<<res<<"\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
412 KB |
Output is correct |
2 |
Correct |
6 ms |
544 KB |
Output is correct |
3 |
Correct |
8 ms |
840 KB |
Output is correct |
4 |
Correct |
6 ms |
888 KB |
Output is correct |
5 |
Correct |
7 ms |
888 KB |
Output is correct |
6 |
Correct |
7 ms |
912 KB |
Output is correct |
7 |
Correct |
8 ms |
1084 KB |
Output is correct |
8 |
Correct |
5 ms |
1136 KB |
Output is correct |
9 |
Correct |
6 ms |
1136 KB |
Output is correct |
10 |
Correct |
6 ms |
1248 KB |
Output is correct |
11 |
Correct |
6 ms |
1332 KB |
Output is correct |
12 |
Correct |
6 ms |
1384 KB |
Output is correct |
13 |
Correct |
7 ms |
1392 KB |
Output is correct |
14 |
Correct |
5 ms |
1544 KB |
Output is correct |
15 |
Correct |
6 ms |
1588 KB |
Output is correct |
16 |
Correct |
6 ms |
1632 KB |
Output is correct |
17 |
Correct |
8 ms |
1632 KB |
Output is correct |
18 |
Correct |
5 ms |
1632 KB |
Output is correct |
19 |
Correct |
2 ms |
1640 KB |
Output is correct |
20 |
Correct |
2 ms |
1644 KB |
Output is correct |
21 |
Correct |
2 ms |
1652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
482 ms |
11608 KB |
Output is correct |
2 |
Correct |
454 ms |
17576 KB |
Output is correct |
3 |
Correct |
473 ms |
23596 KB |
Output is correct |
4 |
Correct |
442 ms |
28448 KB |
Output is correct |
5 |
Correct |
454 ms |
35364 KB |
Output is correct |
6 |
Correct |
390 ms |
40368 KB |
Output is correct |
7 |
Correct |
405 ms |
44852 KB |
Output is correct |
8 |
Correct |
454 ms |
50460 KB |
Output is correct |
9 |
Correct |
452 ms |
56224 KB |
Output is correct |
10 |
Correct |
467 ms |
60500 KB |
Output is correct |
11 |
Correct |
403 ms |
66044 KB |
Output is correct |
12 |
Correct |
400 ms |
71208 KB |
Output is correct |
13 |
Correct |
410 ms |
76448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
412 KB |
Output is correct |
2 |
Correct |
6 ms |
544 KB |
Output is correct |
3 |
Correct |
8 ms |
840 KB |
Output is correct |
4 |
Correct |
6 ms |
888 KB |
Output is correct |
5 |
Correct |
7 ms |
888 KB |
Output is correct |
6 |
Correct |
7 ms |
912 KB |
Output is correct |
7 |
Correct |
8 ms |
1084 KB |
Output is correct |
8 |
Correct |
5 ms |
1136 KB |
Output is correct |
9 |
Correct |
6 ms |
1136 KB |
Output is correct |
10 |
Correct |
6 ms |
1248 KB |
Output is correct |
11 |
Correct |
6 ms |
1332 KB |
Output is correct |
12 |
Correct |
6 ms |
1384 KB |
Output is correct |
13 |
Correct |
7 ms |
1392 KB |
Output is correct |
14 |
Correct |
5 ms |
1544 KB |
Output is correct |
15 |
Correct |
6 ms |
1588 KB |
Output is correct |
16 |
Correct |
6 ms |
1632 KB |
Output is correct |
17 |
Correct |
8 ms |
1632 KB |
Output is correct |
18 |
Correct |
5 ms |
1632 KB |
Output is correct |
19 |
Correct |
2 ms |
1640 KB |
Output is correct |
20 |
Correct |
2 ms |
1644 KB |
Output is correct |
21 |
Correct |
2 ms |
1652 KB |
Output is correct |
22 |
Correct |
482 ms |
11608 KB |
Output is correct |
23 |
Correct |
454 ms |
17576 KB |
Output is correct |
24 |
Correct |
473 ms |
23596 KB |
Output is correct |
25 |
Correct |
442 ms |
28448 KB |
Output is correct |
26 |
Correct |
454 ms |
35364 KB |
Output is correct |
27 |
Correct |
390 ms |
40368 KB |
Output is correct |
28 |
Correct |
405 ms |
44852 KB |
Output is correct |
29 |
Correct |
454 ms |
50460 KB |
Output is correct |
30 |
Correct |
452 ms |
56224 KB |
Output is correct |
31 |
Correct |
467 ms |
60500 KB |
Output is correct |
32 |
Correct |
403 ms |
66044 KB |
Output is correct |
33 |
Correct |
400 ms |
71208 KB |
Output is correct |
34 |
Correct |
410 ms |
76448 KB |
Output is correct |
35 |
Correct |
480 ms |
79616 KB |
Output is correct |
36 |
Correct |
474 ms |
86352 KB |
Output is correct |
37 |
Correct |
479 ms |
92740 KB |
Output is correct |
38 |
Correct |
461 ms |
97904 KB |
Output is correct |
39 |
Correct |
484 ms |
103180 KB |
Output is correct |
40 |
Correct |
456 ms |
108792 KB |
Output is correct |
41 |
Correct |
472 ms |
113896 KB |
Output is correct |
42 |
Correct |
475 ms |
119560 KB |
Output is correct |
43 |
Correct |
493 ms |
124132 KB |
Output is correct |
44 |
Correct |
465 ms |
129848 KB |
Output is correct |
45 |
Correct |
484 ms |
135532 KB |
Output is correct |
46 |
Correct |
554 ms |
142164 KB |
Output is correct |
47 |
Correct |
389 ms |
146640 KB |
Output is correct |
48 |
Correct |
435 ms |
151348 KB |
Output is correct |
49 |
Correct |
453 ms |
154932 KB |
Output is correct |
50 |
Correct |
401 ms |
160160 KB |
Output is correct |
51 |
Correct |
422 ms |
165036 KB |
Output is correct |
52 |
Correct |
434 ms |
169624 KB |
Output is correct |