Cod sursa(job #2476653)

Utilizator Iulia14iulia slanina Iulia14 Data 19 octombrie 2019 10:53:51
Problema Cuburi2 Scor 47
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>

using namespace std;

ifstream cin ("cuburi2.in");
ofstream cout ("cuburi2.out");

int v[250005];
int st[250005];
int dr[250005];
long long  costst[250005];
long long costdr[250005];

int main()
{
    long long n,m,i,poz,x,y,sumst,sumdr,sta,dre,mi,mini=100000000000000000;
    cin>>n>>m;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
        st[i]=st[i-1]+v[i];
        costst[i]=costst[i-1]+st[i-1];
    }
    for (i=n;i>=1;i--)
    {
        dr[i]=dr[i+1]+v[i];
        costdr[i]=costdr[i+1]+dr[i+1];
    }
    for (int h=1;h<=m;h++)
    {
        cin>>x>>y;
        sta=x;
        dre=y;
        mini=st[n]+1;
        while (sta<=dre)
        {
            mi=(sta+dre)/2;
            sumst=st[mi-1]-st[x-1];
            sumdr=st[y]-st[mi-1];
            if (sumst<sumdr){
                sta=mi+1;
                poz=mi;
            }
            else
                dre=mi-1;
        }
        sumst=costst[poz]-costst[x]-st[x-1]*(poz-x);
        sumdr=costdr[poz]-costdr[y]-dr[y+1]*(y-poz);
        cout<<poz<<' '<<sumst+sumdr<<'\n';
    }
    return 0;
}