Cod sursa(job #771385)
#include<stdio.h>
FILE *f = fopen("cuburi2.in","r");
FILE *g = fopen("cuburi2.out","w");
#define MaxN 250100
#define INF 1LL<<58;
#define ll long long
#define formula (ll)(Best_S[i]-(i-x+1)*B_S[x-1]-Best_S[x-1]+Best_D[i]-(y-i+1)*B_D[y+1]-Best_D[y+1])
int N,M,Poz,a,b;
ll Sol;
int A[MaxN];
ll B_S[MaxN],B_D[MaxN],Best_S[MaxN],Best_D[MaxN];
void citire(void)
{
fscanf(f,"%d %d",&N,&M);
for(int i=1;i<=N;i++)
fscanf(f,"%d ",&A[i]);
}
void Preprocesare(void)
{
for(int i=1;i<=N;i++)
{
B_S[i] = B_S[i-1]+A[i];
Best_S[i] = Best_S[i-1]+B_S[i-1];
}
for(int i=N;i;i--)
{
B_D[i] = B_D[i+1]+A[i];
Best_D[i] = Best_D[i+1]+B_D[i+1];
}
}
inline ll Min(int i,int x,int y)
{
return formula;
}
inline int CautBin(int li,int ls)
{
if(li >= ls-1)
{
if(Min(li,a,b) < Min(ls,a,b))
return li;
return ls;
}
if(B_S[(li+ls)/2] -B_S[li-1] < B_S[ls]-B_S[(li+ls)/2-1])
return CautBin((li+ls)/2,ls);
else
return CautBin(li,(li+ls)/2);
}
void Rezolvare(void)
{
Preprocesare();
for(int i=1;i<=M;i++)
{
fscanf(f,"%d %d",&a,&b);
Poz = CautBin(a,b);
fprintf(g,"%d %lld\n",Poz,Min(Poz,a,b));
}
}
int main()
{
citire();
Rezolvare();
}