Cod sursa(job #2155748)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 8 martie 2018 03:08:10
Problema Tribute Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include<fstream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 50050
int d1[N],x,y,curr,d2[N],X[N],Y[N],n,i,j,dim,ax=999999,ay=999999;
int main()
{
    ifstream f("tribute.in");
    f>>n>>x>>y;
    for(i=0;i<n;++i)
        f>>X[i]>>Y[i];
    sort(X,X+n);
    sort(Y,Y+n);
    dim=max(X[n-1],Y[n-1])+2;
    for(i=1;i<dim;++i)
    {
        while(j<n && X[j]<i)
            ++j,++curr;
        d1[i]=d1[i-1]+curr;
    }
    j=n-1;
    curr=0;
    for(i=dim;i>-1;--i)
    {
        while(j>-1 && X[j]>i)
            --j,++curr;
        d2[i]=d2[i+1]+curr;
    }
    for(i=0;i<dim-x;++i)
        ax=min(ax,d1[i]+d2[i+x]);
    memset(d1,0,sizeof(d1));
    memset(d2,0,sizeof(d2));
    j=0;
    curr=0;
    for(i=1;i<dim;++i)
    {
        while(j<n && Y[j]<i)
            ++j,++curr;
        d1[i]=d1[i-1]+curr;
    }
    j=n-1;
    curr=0;
    for(i=dim;i>-1;--i)
    {
        while(j>-1 && Y[j]>i)
            --j,++curr;
        d2[i]=d2[i+1]+curr;
    }
    for(i=0;i<dim-y;++i)
        ay=min(ay,d1[i]+d2[i+y]);
    ofstream g("tribute.out");
    g<<ax+ay;
    return 0;
}