Cod sursa(job #2433013)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 25 iunie 2019 17:41:09
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 5e4 + 7;
const int INF = 1e9;
const int bound = 5e4;

#define int long long

int nrx[DIM];
int nry[DIM];

int distx[DIM];
int disty[DIM];

int solx = INF;
int soly = INF;

main()
{
    int n, l, r;
    in >> n >> l >> r;

    for(int i = 1; i <= n; i++)
    {
        int px, py;
        in >> px >> py;

        nrx[px]++;
        nry[py]++;
    }

    int nrpx = 0;
    int nrpy = 0;

    for(int i = bound; i >= 0; i--)
    {
        distx[i] = distx[i + 1] + nrpx;
        disty[i] = disty[i + 1] + nrpy;

        nrpx += nrx[i];
        nrpy += nry[i];
    }

    int dx = 0;
    int dy = 0;

    nrpx = 0;
    nrpy = 0;

    for(int i = 0; i <= bound; i++)
    {
        dx += nrpx;
        dy += nrpy;

        solx = min(solx, dx + distx[i + l]);
        soly = min(soly, dy + disty[i + r]);

        nrpx += nrx[i];
        nrpy += nry[i];
    }

    out << solx + soly;
}