Cod sursa(job #1685599)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 11 aprilie 2016 19:10:23
Problema Tribute Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>

using namespace std;

ifstream f("tribute.in");
ofstream g("tribute.out");

int AIB[150005], L[150005], C[150005];
int dx, dy, n;
long long sol;
int const oo = 1000000000;

void Read()
{
    int i, x, y;
    f>>n>>dx>>dy;
    for(i=1; i<=n; i++){
        f>>x>>y;
        L[x+50002]++;
        C[y+50002]++;
    }
}

void Update(int pos, int val)
{
    while(pos < 150005){
        AIB[pos] += val;
        pos += pos&(-pos);
    }
}

int Query(int pos)
{
    int sum = 0;
    while(pos){
        sum += AIB[pos];
        pos -= pos&(-pos);
    }
    return sum;
}

void SolveL()
{
    int i, pivot, st, dr, sum, trib, mini, ind;

    for(i=1; i<150005; i++)
        Update(i, L[i]);

    mini = oo;
    if(n % 2 == 1){

        sum = 0;
        for(i=1; sum <= (n/2); i++)
            sum += C[i];
        dr = i-1;
        st = dr - dx;

        for( ; st <= pivot; st++, dr++){
            trib = abs(n - Query(dr) - Query(st - 1));
            if(trib < mini){
                mini = trib;
                ind = st;
            }
        }
    }
    else{

        sum = 0;
        for(i=1; sum < (n/2); i++)
            sum += C[i];
        dr = i-1;
        st = dr - dx;

        sum = 0;
        for(i=1; sum < (n/2)+1; i++)
            sum += C[i];
        pivot = i-1;

        for( ; st < pivot; st++, dr++){
            trib = abs(n - Query(dr) - Query(st - 1));
            if(trib < mini){
                mini = trib;
                ind = st;
            }
        }
    }

    st = ind;
    dr = ind + dx;
    for(i=1; i<st; i++)
        sol += L[i] * abs(st - i);
    for(i=dr+1; i<150005; i++)
        sol += L[i] * abs(dr - i);
}

void SolveC()
{
    int i, pivot, st, dr, sum, trib, mini, ind;

    for(i=1; i<150005; i++)
        AIB[i] = 0;

    for(i=1; i<150005; i++)
        Update(i, C[i]);

    mini = oo;
    if(n % 2 == 1){

        sum = 0;
        for(i=1; sum <= (n/2); i++)
            sum += C[i];
        dr = i-1;
        st = dr - dy;

        for( ; st <= pivot; st++, dr++){
            trib = abs(n - Query(dr) - Query(st - 1));
            if(trib < mini){
                mini = trib;
                ind = st;
            }
        }
    }
    else{

        sum = 0;
        for(i=1; sum < (n/2); i++)
            sum += C[i];
        dr = i-1;
        st = dr - dy;

        sum = 0;
        for(i=1; sum < (n/2)+1; i++)
            sum += C[i];
        pivot = i-1;

        for( ; st <= pivot; st++, dr++){
            trib = abs(n - Query(dr) - Query(st - 1));
            if(trib < mini){
                mini = trib;
                ind = st;
            }
        }
    }

    st = ind;
    dr = ind + dy;
    for(i=1; i<st; i++)
        sol += C[i] * abs(st - i);
    for(i=dr+1; i<150005; i++)
        sol += C[i] * abs(dr - i);
}

int main()
{
    Read();
    SolveL();
    SolveC();
    g<<sol<<"\n";
    return 0;
}