#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=2e5+5;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
long long segtree[nax*4];
long long tab[nax];
void build(int pos,int l,int r){
if(l==r){
segtree[pos]=tab[l];
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
return;
}
void update(int pos,int l,int r,int left,int right,int value){
if(l>r||l>right||r<left) return;
if(l>=left&&r<=right){
segtree[pos]+=value;
return;
}
int mid=(r+l)/2;
update(pos*2+1,l,mid,left,right,value);
update(pos*2+2,mid+1,r,left,right,value);
return;
}
long long query(int pos,int l,int r,int idx){
if(l==r) return segtree[pos];
int mid=(r+l)/2;
if(idx<=mid) return segtree[pos]+query(pos*2+1,l,mid,idx);
else return segtree[pos]+query(pos*2+2,mid+1,r,idx);
}
int main()
{
optimise;
int n,q,s,t;
cin>>n>>q>>s>>t;
for (int i = 0; i <= n; ++i)
{
cin>>tab[i];
}
build(0,0,n);
long long sum=0;
for (int i = 1; i <= n; ++i)
{
if(tab[i-1]<tab[i]) sum+=1ll*s*(tab[i-1]-tab[i]);
else sum+=1ll*t*(tab[i-1]-tab[i]);
}
while(q--){
int l,r,x;
cin>>l>>r>>x;
int left=query(0,0,n,l);
int lefty=query(0,0,n,l-1);
int right=query(0,0,n,r);
int righty;
if(r<n) righty=query(0,0,n,r+1);
update(0,0,n,l,r,x);
if(lefty<left) sum-=1ll*s*(lefty-left);
else sum-=1ll*t*(lefty-left);
int cnt=query(0,0,n,l);
if(lefty<cnt) sum+=1ll*s*(lefty-cnt);
else sum+=1ll*t*(lefty-cnt);
if(r<n){
cnt=query(0,0,n,r);
if(right<righty) sum-=1ll*s*(right-righty);
else sum-=1ll*t*(right-righty);
if(cnt<righty) sum+=1ll*s*(cnt-righty);
else sum+=1ll*t*(cnt-righty);
}
cout <<sum<<endl;
/*if(tab[l-1]<tab[l]) sum+=1ll*s*(tab[l-1]-tab[l]);
else sum+=1ll*t*(tab[l-1]-tab[l]);
cnt=tab[l]+x;
if(tab[l-1]<cnt) sum-=1ll*s*(tab[l-1]-cnt);
else sum-=1ll*t*(tab[l-1]-cnt);
if(r<n){
cnt=tab[r]+x;
if(tab[r]<tab[r+1]) sum+=1ll*s*(tab[r]-tab[r+1]);
else sum+=1ll*t*(tab[r]-tab[r+1]);
if(cnt<tab[r+1]) sum-=1ll*s*(cnt-tab[r+1]);
else sum-=1ll*t*(cnt-tab[r+1]);
}*/
}
}
Compilation message
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:77:47: warning: 'righty' may be used uninitialized in this function [-Wmaybe-uninitialized]
77 | if(right<righty) sum-=1ll*s*(right-righty);
| ~~~~~~^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2392 KB |
Output is correct |
2 |
Correct |
5 ms |
2396 KB |
Output is correct |
3 |
Correct |
4 ms |
2396 KB |
Output is correct |
4 |
Correct |
6 ms |
2652 KB |
Output is correct |
5 |
Correct |
4 ms |
2396 KB |
Output is correct |
6 |
Correct |
4 ms |
2396 KB |
Output is correct |
7 |
Correct |
4 ms |
2648 KB |
Output is correct |
8 |
Correct |
4 ms |
2396 KB |
Output is correct |
9 |
Correct |
4 ms |
2396 KB |
Output is correct |
10 |
Correct |
4 ms |
2588 KB |
Output is correct |
11 |
Correct |
4 ms |
2396 KB |
Output is correct |
12 |
Correct |
5 ms |
2396 KB |
Output is correct |
13 |
Correct |
3 ms |
2396 KB |
Output is correct |
14 |
Correct |
4 ms |
2524 KB |
Output is correct |
15 |
Correct |
4 ms |
2396 KB |
Output is correct |
16 |
Correct |
4 ms |
2396 KB |
Output is correct |
17 |
Correct |
5 ms |
2520 KB |
Output is correct |
18 |
Correct |
4 ms |
2576 KB |
Output is correct |
19 |
Correct |
1 ms |
2392 KB |
Output is correct |
20 |
Correct |
1 ms |
2396 KB |
Output is correct |
21 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
407 ms |
13396 KB |
Output is correct |
2 |
Correct |
438 ms |
14008 KB |
Output is correct |
3 |
Correct |
480 ms |
14648 KB |
Output is correct |
4 |
Correct |
418 ms |
14048 KB |
Output is correct |
5 |
Correct |
435 ms |
15348 KB |
Output is correct |
6 |
Correct |
279 ms |
14396 KB |
Output is correct |
7 |
Correct |
302 ms |
14272 KB |
Output is correct |
8 |
Correct |
388 ms |
14932 KB |
Output is correct |
9 |
Correct |
418 ms |
15440 KB |
Output is correct |
10 |
Correct |
379 ms |
14172 KB |
Output is correct |
11 |
Correct |
337 ms |
14264 KB |
Output is correct |
12 |
Incorrect |
292 ms |
14744 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2392 KB |
Output is correct |
2 |
Correct |
5 ms |
2396 KB |
Output is correct |
3 |
Correct |
4 ms |
2396 KB |
Output is correct |
4 |
Correct |
6 ms |
2652 KB |
Output is correct |
5 |
Correct |
4 ms |
2396 KB |
Output is correct |
6 |
Correct |
4 ms |
2396 KB |
Output is correct |
7 |
Correct |
4 ms |
2648 KB |
Output is correct |
8 |
Correct |
4 ms |
2396 KB |
Output is correct |
9 |
Correct |
4 ms |
2396 KB |
Output is correct |
10 |
Correct |
4 ms |
2588 KB |
Output is correct |
11 |
Correct |
4 ms |
2396 KB |
Output is correct |
12 |
Correct |
5 ms |
2396 KB |
Output is correct |
13 |
Correct |
3 ms |
2396 KB |
Output is correct |
14 |
Correct |
4 ms |
2524 KB |
Output is correct |
15 |
Correct |
4 ms |
2396 KB |
Output is correct |
16 |
Correct |
4 ms |
2396 KB |
Output is correct |
17 |
Correct |
5 ms |
2520 KB |
Output is correct |
18 |
Correct |
4 ms |
2576 KB |
Output is correct |
19 |
Correct |
1 ms |
2392 KB |
Output is correct |
20 |
Correct |
1 ms |
2396 KB |
Output is correct |
21 |
Correct |
1 ms |
2396 KB |
Output is correct |
22 |
Correct |
407 ms |
13396 KB |
Output is correct |
23 |
Correct |
438 ms |
14008 KB |
Output is correct |
24 |
Correct |
480 ms |
14648 KB |
Output is correct |
25 |
Correct |
418 ms |
14048 KB |
Output is correct |
26 |
Correct |
435 ms |
15348 KB |
Output is correct |
27 |
Correct |
279 ms |
14396 KB |
Output is correct |
28 |
Correct |
302 ms |
14272 KB |
Output is correct |
29 |
Correct |
388 ms |
14932 KB |
Output is correct |
30 |
Correct |
418 ms |
15440 KB |
Output is correct |
31 |
Correct |
379 ms |
14172 KB |
Output is correct |
32 |
Correct |
337 ms |
14264 KB |
Output is correct |
33 |
Incorrect |
292 ms |
14744 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |