//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//Abdulhamid Han
//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define int long long
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;
int n,m,b[li],a[li],k,flag,t,ar,az,tree[li*4],lazy[li*4],PS[li],tree1[li*4],lazy1[li*4];
int cev;
string s;
vector<int> v;
inline void push(int node,int start,int end){
if(!lazy[node])return ;
tree[node]+=lazy[node]*(end-start+1);
if(start!=end){
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
inline void build(int node,int start,int end){
if(start>end)return ;
if(start==end){tree[node]=PS[start];return ;}
build(node*2,start,mid),build(node*2+1,mid+1,end);
tree[node]=tree[node*2]+tree[node*2+1];
}
inline void update(int node,int start,int end,int l,int r,int val){
//~ push(node,start,end);
if(start>end || start>r || end<l)return ;
if(start>=l && end<=r){tree[node]=val;return ;}
update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
tree[node]=tree[node*2]+tree[node*2+1];
}
inline int query(int node,int start,int end,int l,int r){
if(start>end || start>r || end<l)return 0;
//~ push(node,start,end);
if(start>=l && end<=r)return tree[node];
return query(node*2,start,mid,l,r)+query(node*2+1,mid+1,end,l,r);
}
inline void push1(int node,int start,int end){
if(lazy1[node]==0)return ;
tree1[node]+=lazy1[node]*(end-start+1);
if(start!=end){
lazy1[node*2]+=lazy1[node];
lazy1[node*2+1]+=lazy1[node];
}
lazy1[node]=0;
}
inline void build1(int node,int start,int end){
if(start>end)return ;
if(start==end){tree1[node]=a[start];return ;}
build1(node*2,start,mid),build1(node*2+1,mid+1,end);
tree1[node]=tree1[node*2]+tree1[node*2+1];
}
inline void update1(int node,int start,int end,int l,int r,int val){
if(start>end || start>r || end<l)return ;
push1(node,start,end);
if(start>=l && end<=r){lazy1[node]+=val;push1(node,start,end);return ;}
update1(node*2,start,mid,l,r,val),update1(node*2+1,mid+1,end,l,r,val);
tree1[node]=tree1[node*2]+tree1[node*2+1];
}
inline int query1(int node,int start,int end,int l,int r){
if(start>end || start>r || end<l)return 0;
push1(node,start,end);
if(start>=l && end<=r)return tree1[node];
return query1(node*2,start,mid,l,r)+query1(node*2+1,mid+1,end,l,r);
}
main(void){
scanf("%lld %lld %lld %lld",&n,&t,&az,&ar);
////~ scanf("%d",&m);
for(int i=1;i<=n+1;i++){
scanf("%lld",&a[i]);
int at=0;
if(i==1)continue;
if(a[i-1]>=a[i])at+=(a[i-1]-a[i])*ar;
if(a[i-1]<a[i])at-=(a[i]-a[i-1])*az;
PS[i]=at;
}
for(int i=1;i<=n;i++)PS[i]=PS[i+1];
PS[n+1]=0;
n++;
build(1,1,n);
build1(1,1,n);
////~ cout<<query(1,1,n,3,4)<<endl;
while(t--){
int l,r,x;
scanf("%lld %lld %lld",&l,&r,&x);
l++;
r++;
cev=query(1,1,n,1,l-2);
cev+=query(1,1,n,r+1,n);
cev+=query(1,1,n,l,r-1);
update1(1,1,n,l,r,x);
int l1=query1(1,1,n,l-1,l-1);
int l2=query1(1,1,n,l,l);
//~ r1=query1(1,1,n,r,r);
int r2=0,r1=0;
if(r<n){
r2=query1(1,1,n,r+1,r+1);
r1=query1(1,1,n,r,r);
}
if(l1>=l2)cev+=(l1-l2)*ar;
if(l1<l2)cev-=(l2-l1)*az;
////~ cout<<cev<<endl;
if(r<n){
if(r2>r1)cev-=(r2-r1)*az;
if(r2<=r1)cev+=(r1-r2)*ar;
}
if(l1>=l2)update(1,1,n,l-1,l-1,(l1-l2)*ar);
if(l1<l2)update(1,1,n,l-1,l-1,-(l2-l1)*az);
if(r<n){
if(r2>r1)update(1,1,n,r,r,-(r2-r1)*az);
if(r2<=r1)update(1,1,n,r,r,(r1-r2)*ar);
}
////~ update(1,1,n,l-1,l-1,x);
////~ update(1,1,n,r,r,x);
printf("%lld\n",cev);
}
return 0;
}
Compilation message
foehn_phenomena.cpp:107:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(void){
^
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld %lld",&n,&t,&az,&ar);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&a[i]);
~~~~~^~~~~~~~~~~~~~
foehn_phenomena.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld",&l,&r,&x);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
504 KB |
Output is correct |
2 |
Correct |
10 ms |
504 KB |
Output is correct |
3 |
Correct |
10 ms |
504 KB |
Output is correct |
4 |
Correct |
10 ms |
504 KB |
Output is correct |
5 |
Correct |
10 ms |
504 KB |
Output is correct |
6 |
Correct |
10 ms |
504 KB |
Output is correct |
7 |
Correct |
11 ms |
632 KB |
Output is correct |
8 |
Correct |
10 ms |
504 KB |
Output is correct |
9 |
Correct |
10 ms |
504 KB |
Output is correct |
10 |
Correct |
10 ms |
504 KB |
Output is correct |
11 |
Correct |
10 ms |
504 KB |
Output is correct |
12 |
Correct |
10 ms |
508 KB |
Output is correct |
13 |
Correct |
7 ms |
504 KB |
Output is correct |
14 |
Correct |
7 ms |
504 KB |
Output is correct |
15 |
Correct |
10 ms |
504 KB |
Output is correct |
16 |
Correct |
8 ms |
504 KB |
Output is correct |
17 |
Correct |
7 ms |
504 KB |
Output is correct |
18 |
Correct |
8 ms |
504 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
944 ms |
17304 KB |
Output is correct |
2 |
Correct |
965 ms |
23416 KB |
Output is correct |
3 |
Correct |
976 ms |
24088 KB |
Output is correct |
4 |
Correct |
959 ms |
23416 KB |
Output is correct |
5 |
Correct |
974 ms |
24568 KB |
Output is correct |
6 |
Correct |
314 ms |
19320 KB |
Output is correct |
7 |
Correct |
317 ms |
19320 KB |
Output is correct |
8 |
Correct |
795 ms |
24312 KB |
Output is correct |
9 |
Correct |
788 ms |
24568 KB |
Output is correct |
10 |
Correct |
784 ms |
23544 KB |
Output is correct |
11 |
Correct |
419 ms |
19404 KB |
Output is correct |
12 |
Correct |
309 ms |
20088 KB |
Output is correct |
13 |
Correct |
335 ms |
20216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
504 KB |
Output is correct |
2 |
Correct |
10 ms |
504 KB |
Output is correct |
3 |
Correct |
10 ms |
504 KB |
Output is correct |
4 |
Correct |
10 ms |
504 KB |
Output is correct |
5 |
Correct |
10 ms |
504 KB |
Output is correct |
6 |
Correct |
10 ms |
504 KB |
Output is correct |
7 |
Correct |
11 ms |
632 KB |
Output is correct |
8 |
Correct |
10 ms |
504 KB |
Output is correct |
9 |
Correct |
10 ms |
504 KB |
Output is correct |
10 |
Correct |
10 ms |
504 KB |
Output is correct |
11 |
Correct |
10 ms |
504 KB |
Output is correct |
12 |
Correct |
10 ms |
508 KB |
Output is correct |
13 |
Correct |
7 ms |
504 KB |
Output is correct |
14 |
Correct |
7 ms |
504 KB |
Output is correct |
15 |
Correct |
10 ms |
504 KB |
Output is correct |
16 |
Correct |
8 ms |
504 KB |
Output is correct |
17 |
Correct |
7 ms |
504 KB |
Output is correct |
18 |
Correct |
8 ms |
504 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
944 ms |
17304 KB |
Output is correct |
23 |
Correct |
965 ms |
23416 KB |
Output is correct |
24 |
Correct |
976 ms |
24088 KB |
Output is correct |
25 |
Correct |
959 ms |
23416 KB |
Output is correct |
26 |
Correct |
974 ms |
24568 KB |
Output is correct |
27 |
Correct |
314 ms |
19320 KB |
Output is correct |
28 |
Correct |
317 ms |
19320 KB |
Output is correct |
29 |
Correct |
795 ms |
24312 KB |
Output is correct |
30 |
Correct |
788 ms |
24568 KB |
Output is correct |
31 |
Correct |
784 ms |
23544 KB |
Output is correct |
32 |
Correct |
419 ms |
19404 KB |
Output is correct |
33 |
Correct |
309 ms |
20088 KB |
Output is correct |
34 |
Correct |
335 ms |
20216 KB |
Output is correct |
35 |
Correct |
971 ms |
22904 KB |
Output is correct |
36 |
Correct |
997 ms |
24184 KB |
Output is correct |
37 |
Correct |
986 ms |
25108 KB |
Output is correct |
38 |
Correct |
975 ms |
24824 KB |
Output is correct |
39 |
Correct |
972 ms |
24952 KB |
Output is correct |
40 |
Correct |
984 ms |
24952 KB |
Output is correct |
41 |
Correct |
985 ms |
24824 KB |
Output is correct |
42 |
Correct |
990 ms |
24960 KB |
Output is correct |
43 |
Correct |
959 ms |
24184 KB |
Output is correct |
44 |
Correct |
970 ms |
24568 KB |
Output is correct |
45 |
Correct |
935 ms |
24568 KB |
Output is correct |
46 |
Correct |
987 ms |
25668 KB |
Output is correct |
47 |
Correct |
315 ms |
20088 KB |
Output is correct |
48 |
Correct |
439 ms |
19960 KB |
Output is correct |
49 |
Correct |
974 ms |
23288 KB |
Output is correct |
50 |
Correct |
407 ms |
19832 KB |
Output is correct |
51 |
Correct |
308 ms |
20216 KB |
Output is correct |
52 |
Correct |
464 ms |
20364 KB |
Output is correct |