# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1256850 | blankcodes | Secret (JOI14_secret) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int N, bsz, arr[1000000], blk[1001];
inline int op(int x,int y){return x+y;}
void Init(int n,int a[]){
N=n;
bsz=(int)sqrt(N)+1;
memcpy(arr,a,sizeof(int)*N);
fill(blk,blk+bsz,0);
for(int i=0;i<N;i++) blk[i/bsz]=op(blk[i/bsz],arr[i]);
}
int Query(int L,int R){
int res=0;
while(L<=R && L%bsz){
res=op(res,arr[L++]);
}
while(L+bsz-1<=R){
res=op(res,blk[L/bsz]);
L+=bsz;
}
while(L<=R) res=op(res,arr[L++]);
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin>>n;
static int a[1000000];
for(int i=0;i<n;i++) cin>>a[i];
Init(n,a);
int q; cin>>q;
while(q--){
int L,R; cin>>L>>R;
cout<<Query(L,R)<<"\n";
}
}