Cod sursa(job #270261)
# include <stdio.h>
# define N 250001
long long a[N],A[N],b[N],B[N],ct;
int i,v[N],n,m,x,y,nr;
int BS(int st, int dr)
{ int i=st,j=dr,m,P=0;
while (i<=j) {
m=i+(j-i)/2;
if (A[m-1]-A[x-1]<A[y]-A[m-1]){
i=m+1; P=m;
}
else dr=m-1;
}
return P;
}
int main(){
freopen("cuburi2.in", "r", stdin);
freopen("cuburi2.out", "w", stdout);
scanf("%d %d",&n,&m);
for (i=1;i<=n;++i){
scanf("%lld ",&v[i]);
a[i]=a[i-1]+v[i];
A[i]=A[i-1]+a[i-1];
}
for (i=n;i>=1;--i){
b[i]=b[i+1]+v[i];
B[i]=B[i+1]+b[i+1];
}
for (i=1;i<=m;++i){
scanf("%d %d",&x,&y);
nr=BS(x,y);
ct=A[nr-1]-A[x-1]-a[x-1]*(nr-x)+B[nr+1]-B[y+1]-b[y+1]*(y-nr);
printf("%d %lld", nr, ct);
}
return 0;
}