Submission #471879

#TimeUsernameProblemLanguageResultExecution timeMemory
471879Sho10Addk (eJOI21_addk)C++17
0 / 100
86 ms5168 KiB
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho #define ll long long #define double long double #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #define aint(a) (a).begin(), (a).end() #define f first #define s second #define pb push_back #define mp make_pair #define pi pair #define rc(s) return cout<<s,0 #define endl '\n' #define mod 998244353 #define PI 3.14159265359 #define INF 1000000005 #define LINF 1000000000000000005ll #define CODE_START ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; ll n,a[100005],k,q,preff[100005],suff[100005]; struct tr{ ll sum,pref,suf; }; tr tree[400005]; tr gol; tr uni(tr x,tr y){ tr ans; ans.sum=x.sum+y.sum; ans.pref=x.pref+y.pref; ans.suf=y.suf+x.suf; return ans; } void build(ll node,ll l,ll r){ if(l==r){ tree[node].sum=a[l]; tree[node].pref=preff[l]; tree[node].suf=suff[r]; return; } ll mid=(l+r)/2; build(2*node,l,mid); build(2*node+1,mid+1,r); tree[node]=uni(tree[2*node],tree[2*node+1]); } ll querysum(ll node,ll l,ll r,ll st,ll dr){ if(l>dr){ return 0; } if(r<st){ return 0; } if(st<=l&&r<=dr){ return tree[node].sum; } ll mid=(l+r)/2; return querysum(2*node,l,mid,st,dr)+querysum(2*node+1,mid+1,r,st,dr); } tr query(ll node,ll l,ll r,ll pos){ if(l==r){ return tree[node]; } ll mid=(l+r)/2; if(pos<=mid){ return query(2*node,l,mid,pos); }else { return query(2*node+1,mid+1,r,pos); } } int32_t main(){ CODE_START; cin>>n>>k; gol.sum=0; gol.pref=0; gol.suf=0; for(ll i=1;i<=n;i++) { cin>>a[i]; } for(ll i=1;i<=n;i++) { preff[i]=preff[i-1]+a[i]*i; } for(ll i=n;i>=1;i--) suff[i]=suff[i+1]+a[i]*(n-i+1); build(1,1,n); cin>>q; while(q--){ ll type; cin>>type; if(type==1){ ll x; cin>>x; continue; } ll l,r,m; cin>>l>>r>>m; if(l==r){ cout<<querysum(1,1,n,l,r)<<endl; continue; } if(r-l+1>=2*m-1){ // cout<<"DA"<<endl; cout<<query(1,1,n,l+m-1).pref-query(1,1,n,l-1).pref-querysum(1,1,n,l,l+m-1)*(l-1)+query(1,1,n,r-m+1).suf-query(1,1,n,r+1).suf-querysum(1,1,n,r-m+1,r)*(n-r)+querysum(1,1,n,l+m,r-m)*m<<endl; }else { ll mid=(r-l+1)/2; cout<<query(1,1,n,l+mid-1).pref-query(1,1,n,l-1).pref-querysum(1,1,n,l,l+mid-1)*(l-1)+query(1,1,n,l+mid).suf-query(1,1,n,r+1).suf-querysum(1,1,n,l+mid,r)*(n-r)<<endl; } } } /* 8 3 7 2 5 1 9 3 4 6 2 2 2 7 4 2 2 7 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...