#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
#define printl(args...) printf(args)
#else
#define printl(args...) 0
#endif
struct SegmentTree{
vector<ll>tree;
void build(int n){
tree.assign(n<<2|3,0);
}
ll get(int v,int l,int r,int ql,int qr){
if(qr<l||r<ql)return 0ll;
if(ql<=l&&r<=qr)return tree[v];
int mid=(l+r)>>1;
return get(v<<1,l,mid,ql,qr)+get(v<<1|1,mid+1,r,ql,qr);
}
void update(int v,int l,int r,int pos,ll val){
if(l==r){
tree[v]=val;
return;
}
int mid=(l+r)>>1;
if(pos>mid)update(v<<1|1,mid+1,r,pos,val);
else update(v<<1,l,mid,pos,val);
tree[v]=tree[v<<1]+tree[v<<1|1];
}
}tree[3];
ll a[100005];
int main(){
int n,k,q;
scanf("%d%d",&n,&k);
tree[0].build(n);
tree[1].build(n);
tree[2].build(n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
a[i]=x;
tree[0].update(1,1,n,i,a[i]);
tree[1].update(1,1,n,i,a[i]*i);
tree[2].update(1,1,n,i,a[i]*(n-i+1));
}
scanf("%d",&q);
while(q--){
int type;
scanf("%d",&type);
if(type&1){
//SOON
scanf("%d",&type);
}else{
int l,r,m;
ll ans=0;
scanf("%d%d%d",&l,&r,&m);
if(2*m>r-l+1)m=r-l+2-m;
ans+=tree[1].get(1,1,n,l,l+m-1)-tree[0].get(1,1,n,l,l+m-1)*1ll*(l-1);
ans+=tree[2].get(1,1,n,r-m+1,r)-tree[0].get(1,1,n,r-m+1,r)*1ll*(n-r);
if(2*m-1==r-l+1)ans-=m*a[l+r>>1];
else ans+=tree[0].get(1,1,n,l+m,r-m)*(1ll*m);
printl("________________");
printf("%lld\n",ans);
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:71:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | if(2*m-1==r-l+1)ans-=m*a[l+r>>1];
| ~^~
Main.cpp:18:29: warning: statement has no effect [-Wunused-value]
18 | #define printl(args...) 0
| ^
Main.cpp:73:4: note: in expansion of macro 'printl'
73 | printl("________________");
| ^~~~~~
Main.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%d%d",&n,&k);
| ~~~~~^~~~~~~~~~~~~~
Main.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
Main.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
Main.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d",&type);
| ~~~~~^~~~~~~~~~~~
Main.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%d",&type);
| ~~~~~^~~~~~~~~~~~
Main.cpp:67:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d%d%d",&l,&r,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
5 ms |
468 KB |
Output is correct |
| 4 |
Correct |
7 ms |
648 KB |
Output is correct |
| 5 |
Correct |
7 ms |
724 KB |
Output is correct |
| 6 |
Correct |
9 ms |
852 KB |
Output is correct |
| 7 |
Correct |
13 ms |
992 KB |
Output is correct |
| 8 |
Correct |
13 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
17 ms |
1364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
2572 KB |
Output is correct |
| 2 |
Correct |
57 ms |
3668 KB |
Output is correct |
| 3 |
Correct |
107 ms |
4856 KB |
Output is correct |
| 4 |
Correct |
153 ms |
8396 KB |
Output is correct |
| 5 |
Correct |
238 ms |
11956 KB |
Output is correct |
| 6 |
Correct |
191 ms |
11804 KB |
Output is correct |
| 7 |
Correct |
233 ms |
11728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
5804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
