Pagini recente » Cod sursa (job #2147539) | Cod sursa (job #1801726) | Cod sursa (job #1039263) | Cod sursa (job #2266901) | Cod sursa (job #1002700)
#include<stdio.h>
int n,v[250002],aux[250002],sd[250002],ss[250002];
int st,dr,x,y;
inline int caut(int l1,int l2)
{
int m;
st=x;dr=y;
while(st<dr)
{
m=(st+dr)/2;
if(v[m]-l1>aux[m]-l2)
dr=m;
else
st=m+1;
}
return st;
}
int main()
{
freopen("cuburi2.in","r",stdin);
freopen("cuburi2.out","w",stdout);
int m,i,j,s=0,sol1;
long long sol2;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
{
scanf("%d",&ss[i]);
s+=ss[i];
}
for(i=1;i<=n;++i)
{
v[i]=v[i-1]+ss[i];
aux[i]=s-v[i];
}
for(i=1;i<=n;++i)
ss[i]=ss[i-1]+v[i-1];
for(i=n;i>0;--i)
sd[i]=sd[i+1]+aux[i];
//////////////////////////////
while(m--)
{
scanf("%d%d",&x,&y);
sol1=caut(v[x-1],aux[y]);
sol2=(long long)ss[sol1]-ss[x]-v[x-1]*(sol1-x);
sol2=sol2+(long long)sd[sol1]-sd[y]-aux[y]*(y-sol1);
printf("%d %lld\n",sol1,sol2);
}
return 0;
}