제출 #843709

#제출 시각아이디문제언어결과실행 시간메모리
843709Andrijanikolic73Addk (eJOI21_addk)C++17
92 / 100
213 ms6760 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N=1e5+50; int t[2*N]; int query(int i){int ans=0;for(;i>0;i-=i&-i)ans+=t[i];return ans;} void update(int i,int v){for(;i<N;i+=i&-i)t[i]+=v;} int query(int l,int r){ if(l>r)return 0; if(l==0)return query(r); return query(r)-query(l-1); } signed main(){ int n,k; cin>>n>>k; int a[n+1]; for(int i=1;i<=n;i++)cin>>a[i]; int pref[n+1]; pref[0]=0; for(int i=1;i<=n;i++)pref[i]=pref[i-1]+a[i]; int q; cin>>q; if(max(n,q)<=10000&&k==1){ while(q--){ int o; cin>>o; if(o==1){ int X; cin>>X; continue; } int l,r,m; cin>>l>>r>>m; int ans=0; // i>r-m+1 //for(int i=l;i<=r-m+1;i++)ans+=pref[i+m-1]-pref[i-1];. for(int i=r;i>=l+m-1;i--){ ans+=pref[i]; } for(int i=l-1;i<=r-m;i++)ans-=pref[i]; cout<<ans; cout<<endl; } return 0; } if(k==1){ for(int i=1;i<=n;i++)update(i,pref[i]); while(q--){ int o; cin>>o; if(o==1){ int X; cin>>X; continue; } int l,r,m; cin>>l>>r>>m; int ans=query(l+m-1,r); ans-=query(l-1,r-m); cout<<ans; cout<<endl; } } } /* 8 1 7 2 5 1 9 3 4 6 1 2 2 7 4 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...