Cod sursa(job #1182638)

Utilizator tudormaximTudor Maxim tudormaxim Data 6 mai 2014 23:20:06
Problema Cuburi2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <algorithm>
#include <iostream>
#define ll long long
#define NMAX 250001
using namespace std;

ll n,m,poz,x,y;
ll v[NMAX],nl[NMAX],nr[NMAX],cl[NMAX],cr[NMAX];

inline void bs(int left,int right)
{
    int mid;

	if (left>right)
		return;
	mid=(left+right)/2;

	if (nl[mid-1]-nl[x-1]<nl[y]-nl[mid-1])
	{
		poz=mid;
		bs(mid+1,right);
	}
	else
        bs(left,mid-1);
}

int main()
{
    ll i,ml,mr;

	freopen("cuburi2.in","r",stdin);
	freopen("cuburi2.out","w",stdout);

	cin>>n>>m;
	for (i=1;i<=n;i++)
	{
		cin>>v[i];
		nl[i]=nl[i-1]+v[i];
		cl[i]=cl[i-1]+nl[i-1];
	}

	for (i=n;i>0;i--)
	{
		nr[i]=nr[i+1]+v[i];
		cr[i]=cr[i+1]+nr[i+1];
	}
    while(m)
	{
		cin>>x>>y;
		if (x>y)
			swap(x,y);
		bs(x,y);
		ml=cl[poz]-(poz-x)*nl[x-1]-cl[x];
		mr=cr[poz]-(y-poz)*nr[y+1]-cr[y];
		cout<<poz<<" "<<ml+mr<<"\n";
		m--;
	}

	return 0;
}