Cod sursa(job #2112255)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 23 ianuarie 2018 11:41:07
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
pair <int,int> v[50001];
int main()
{
    int n,dx,dy,i,j,sxmin,sx,symin,sy,k,a,b;
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    scanf("%d%d%d",&n,&dx,&dy);
    for(i=1; i<=n; i++)
        scanf("%d%d",&v[i].x,&v[i].y);
    sort(v+1,v+1+n,[](pair<int,int> a,pair<int,int> b){return a.x<b.x;});
    for(j=1; j<=n && v[j].x<=dx; j++);
    i=0;
    sxmin=sx=0;
    for(k=j; k<=n; k++)
        sxmin+=(v[k].x-dx),sx+=(v[k].x-dx);
    a=0;
    b=dx;
    while(i<=n)
    {
        a++;
        b++;
        sx-=(n-j+1);
        while(j<=n && v[j].x<=b)
            j++;
        while(i<=j && v[i].x<a)
            i++;
        sx+=(i-1);
        if(sx<sxmin)
            sxmin=sx;
    }
    sort(v+1,v+1+n,[](pair<int,int> a,pair<int,int> b){return a.y<b.y;});
    for(j=1; j<=n && v[j].y<=dy; j++);
    i=0;
    symin=sy=0;
    for(k=j; k<=n; k++)
        symin+=(v[k].y-dy),sy+=(v[k].y-dy);
    a=0;
    b=dy;
    while(i<=n)
    {
        a++;
        b++;
        sy-=(n-j+1);
        while(j<=n && v[j].y<=b)
            j++;
        while(i<=j && v[i].y<a)
            i++;
        sy+=(i-1);
        if(sy<symin)
            symin=sy;
    }
    printf("%d\n",sxmin+symin);;

    return 0;
}