Cod sursa(job #2208180)

Utilizator giotoPopescu Ioan gioto Data 28 mai 2018 15:53:16
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>
using namespace std;

int n, dx, dy;
struct aib{
    int v[50005];
    int nr[50005];
    inline void U(int val, int pos){
        for(int i = pos; i <= 50002 ; i += (i & (-i))){
            v[i] += val;
            nr[i] += 1;
        }
    }
    inline pair <int, int> Q(int pos){
        pair <int, int> ans;
        for(int i = pos; i != 0 ; i -= (i & (-i))){
            ans.first += v[i];
            ans.second += nr[i];
        }
        return ans;
    }
};
aib ax;
aib ay;
int main()
{
    freopen("tribute.in", "r", stdin);
    freopen("tribute.out", "w", stdout);

    scanf("%d%d%d", &n, &dx, &dy);
    ++dx; ++dy;
    int x, y;
    for(int i = 1; i <= n ; ++i){
        scanf("%d%d", &x, &y);
        ++x; ++y;
        ax.U(x, x); ay.U(y, y);
    }

    long long solx = 1000000000000000000;
    long long val;
    pair <int, int> aux;
    pair <int, int> aux2;
    for(int i = 1; i <= 50001 - dx + 1; ++i){
        val = 0;
        aux = ax.Q(i - 1);
        val = val + (1LL * aux.second * i - aux.first);

        aux2 = ax.Q(50001);
        aux = ax.Q(i + dx - 1);
        aux2.first -= aux.first;
        aux2.second -= aux.second;

        val = val + (aux2.first - 1LL * aux2.second * (i + dx - 1));
        if(val < solx) solx = val;
    }


    long long soly = 1000000000000000000;
    for(int i = 1; i <= 50001 - dy + 1; ++i){
        val = 0;
        aux = ay.Q(i - 1);
        val = val + (1LL * aux.second * i - aux.first);

        aux2 = ay.Q(50001);
        aux = ax.Q(i + dy - 1);
        aux2.first -= aux.first;
        aux2.second -= aux.second;

        val = val + (aux2.first - 1LL * aux2.second * (i + dy - 1));
        if(val < soly) soly = val;
    }

    printf("%lld", solx + soly);
    return 0;
}