Cod sursa(job #270967)

Utilizator Mishu91Andrei Misarca Mishu91 Data 4 martie 2009 19:07:08
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#include <cstring>

#define MAX_N 50005
#define lsb(x) x & (-x)

int X[MAX_N], Y[MAX_N], A[MAX_N];
int N, dx, dy;

void citire()
{
    scanf("%d %d %d\n",&N, &dx, &dy);

    for(int i = 1; i <= N; ++i)
    {
        scanf("%d %d",X+i, Y+i);
        ++X[i];
        ++Y[i];
    }
}

void update(int x)
{
    for(; x <= MAX_N; x += lsb(x))
        ++A[x];
}

long long sum(int x)
{
    long long sol = 0;
    for(; x; x -= lsb(x))
        sol += A[x];
    return sol;
}

long long solve(int X[MAX_N], int d)
{
    memset(A, 0, sizeof A);

    for(int i = 1; i <= N; ++i)
        update(X[i]);

    long long S = 0;
    int min = MAX_N, max = 0;

    for(int i = 1; i <= N; ++i)
    {
        if(X[i] > max) max = X[i];
        if(X[i] < min) min = X[i];
    }

    for(int i = 1; i <= N; ++i)
        if(X[i] > min + d)
            S += (X[i] - min - d);
    long long smin = S;

    for(int i = min + 1; i <= max - dx; ++i)
    {
        S += sum(i-1);
        S -= sum(max) - sum(i + dx - 1);

        if(smin > S) smin = S;
    }
    return smin;
}

int main()
{
    freopen("tribute.in","rt",stdin);
    freopen("tribute.out","wt",stdout);

    citire();
    printf("%lld\n",solve(X,dx) + solve(Y,dy));
}