Cod sursa(job #1849936)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 17 ianuarie 2017 23:06:52
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
int x[50001],y[50001];
int rezx_st[50001],rezx_dr[50001],rezy_st[50001],rezy_dr[50001];
int main()
{
    int n,dx,dy,i,j,k,minx,miny,lin,col;
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    scanf("%d%d%d",&n,&dx,&dy);
    for(i=1; i<=n; i++)
        scanf("%d%d",&x[i],&y[i]);
    sort(x+1,x+1+n);
    sort(y+1,y+1+n);
    for(i=1; i<=n;)
    {
        j=i;
        while(j<=n && x[j]==x[i])
            j++;
        for(k=x[i]+1; k<=x[j]; k++)
            rezx_st[k]=rezx_st[k-1]+j-1;
        i=j;
    }
    for(k=x[n]+1; k<=50000; k++)
        rezx_st[k]=rezx_st[k-1]+n;
    for(i=n; i>0;)
    {
        j=i;
        while(j>0 && x[j]==x[i])
            j--;
        for(k=x[i]-1; k>=x[j]; k--)
            rezx_dr[k]=rezx_dr[k+1]+n-j;
        i=j;
    }
    for(k=x[1]-1; k>=0; k--)
        rezx_dr[k]=rezx_dr[k+1]+n;
    for(i=1; i<=n;)
    {
        j=i;
        while(j<=n && y[j]==y[i])
            j++;
        for(k=y[i]+1; k<=y[j]; k++)
            rezy_st[k]=rezy_st[k-1]+j-1;
        i=j;
    }
    for(k=y[n]+1; k<=50000; k++)
        rezy_st[k]=rezy_st[k-1]+n;
    for(i=n; i>0;)
    {
        j=i;
        while(j>0 && y[j]==y[i])
            j--;
        for(k=y[i]-1; k>=y[j]; k--)
            rezy_dr[k]=rezy_dr[k+1]+n-j;
        i=j;
    }
    for(k=y[1]-1; k>=0; k--)
        rezy_dr[k]=rezy_dr[k+1]+n;
    minx=miny=2000000000;
    lin=0;
    col=0;
    for(i=0; i<=50000; i++)
    {
        if(i+dx<=50000 && rezx_st[i]+rezx_dr[i+dx]<minx)
        {
            minx=rezx_st[i]+rezx_dr[i+dx];
            lin=i;
        }
        if(i+dy<=50000 && rezy_st[i]+rezy_dr[i+dy]<miny)
        {
            miny=rezy_st[i]+rezy_dr[i+dy];
            col=i;
        }
    }
    printf("%d\n",minx+miny);
    //printf("%d %d\n",lin,col);

    return 0;
}