Pagini recente » Cod sursa (job #2010805) | Cod sursa (job #270967)
Cod sursa(job #270967)
#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));
}