Cod sursa(job #2063452)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 11 noiembrie 2017 11:40:23
Problema Tribute Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("tribute.in");
ofstream g("tribute.out");
long long n,x,y;
struct ox
{
    long long val;
    long long sum;
};
ox v[50002];
ox v2[50002];
bool test(ox a, ox b)
{
    return a.val<b.val;
}
int main()
{
    f>>n>>x>>y;
    for(long long i=1;i<=n;++i)
        f>>v[i].val>>v2[i].val;
    sort(v+1,v+n+1,test);
    sort(v2+1,v2+n+1,test);
    for(long long i=1;i<=n;++i){
        v2[i].sum=v2[i].val+v2[i-1].sum;
        v[i].sum=v[i].val+v[i-1].sum;
    }
    long long ss=1e12;
    long long lmin=0;
    v[n+1].val=1e9;
    v2[n+1].val=1e9;
    for(long long i=x;i<=v[n].val;++i)
    {
        long long b=1;
        long long e=n;
        long long prd=0;
        while(b<=e)
        {
            long long m=(b+e)/2;
            if(v[m].val<=i-x && v[m+1].val>i-x)
            {
                prd+=1ll*m*(i-x)-v[m].sum;
                break;
            }
            else
                if(v[m].val>i-x)
                    e=m-1;
                else
                    b=m+1;
        }
        e=n;
        b=1;
        while(b<=e)
        {
            long long m=(b+e)/2;
            if(v[m].val>i && v[m-1].val<=i)
            {
                prd+=(v[n].sum-v[m-1].sum)-1ll*(n-m+1)*i;
                break;
            }
            else
                if(v[m].val<=i)
                    b=m+1;
                else
                    e=m-1;
        }
        if(prd<ss)
            ss=prd,lmin=i;
    }
    long long ss2=1e12;
    long long cmin=0;
    for(long long i=y;i<=v2[n].val;++i)
    {
        long long b=1;
        long long e=n;
        long long prd=0;
        while(b<=e)
        {
            long long m=(b+e)/2;
            if(v2[m].val<=i-y && v2[m+1].val>i-y)
            {
                prd+=1ll*m*(i-y)-v2[m].sum;
                break;
            }
            else
                if(v2[m].val>i-y)
                    e=m-1;
                else
                    b=m+1;
        }
        e=n;
        b=1;
        while(b<=e)
        {
            long long m=(b+e)/2;
            if(v2[m].val>i && v2[m-1].val<=i)
            {
                prd+=(v2[n].sum-v2[m-1].sum)-1ll*(n-m+1)*i;
                break;
            }
            else
                if(v2[m].val<=i)
                    b=m+1;
                else
                    e=m-1;
        }
        if(prd<ss2)
            ss2=prd,cmin=i;
    }
    g<<ss+ss2;
//    g<<ss<<" "<<lmin<<'\n';
  //  g<<ss2<<" "<<cmin<<'\n';
    return 0;
}