Cod sursa(job #2408318)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 17 aprilie 2019 20:09:37
Problema Ograzi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <cstdio>
#include <algorithm>

#define MAXN 50000
#define MAXM 1000000
#define MAXX 1000000

using namespace std;

char buff[4096];
int p=4095;

inline char get_char()
{
    if( ++p==4096 )
        p=0, fread(buff,1,4096,stdin);

    return buff[p];
}

inline int get_int()
{
    char ch=get_char();

    int k=0;

    while( ch!=' ' && ch!='\n' && ch!=EOF )
        k=k*10+(ch-'0'), ch=get_char();

    return k;
}

struct Puncte
{
    int x, y;
    bool oaie, semn;
};

int l, ans;
Puncte v[1+2*MAXN+MAXM+1];

int aib[1+MAXX+5];

inline void update( int poz )
{
    for( int i=poz;i<=l;i+=(i&(-i)) )
        aib[i]++;
}

inline int query( int poz )
{
    int ans=0;

    for( int i=poz;i>0;i-=(i&(-i)) )
        ans+=aib[i];

    return ans;
}

bool cmp( Puncte a, Puncte b )
{
    if( a.y==b.y )
    {
        if( a.oaie==b.oaie )
        {
            if( a.oaie==false )
                return (a.semn==false && b.semn==true);
            else
                return a.x<b.x;
        }
        else
            return (a.oaie==false);
    }

    return a.y<b.y;
}

int main()
{
    freopen( "ograzi.in", "r", stdin );
    freopen( "ograzi.out", "w", stdout );

    int n, m, w, h;

    n=get_int();
    m=get_int();
    w=get_int();
    h=get_int();

    for( int i=1;i<=n;i++ )
    {
        v[i].x=get_int();
        v[i].y=get_int();

        v[i].x+=2;
        v[i].semn=false;

        v[n+i].x=v[i].x;
        v[n+i].y=v[i].y+h;
        v[n+i].semn=true;

        v[i].oaie=v[n+i].oaie=false;
    }

    for( int i=1;i<=m;i++ )
    {
        v[2*n+i].x=get_int();
        v[2*n+i].y=get_int();

        v[2*n+i].x+=2;

        v[2*n+i].oaie=true;
    }

    l=2*n+m;

    sort(v+1,v+l+1,cmp);

    for( int i=1;i<=l;i++ )
    {
        int height=v[i].y, j=i;

        while( j<=l && v[j].y==height )
        {
            if (!v[j].oaie) {
                if (!v[j].semn)
                    ans -= query(v[j].x + w) - query(v[j].x - 1);
                else
                    ans += query(v[j].x + w) - query(v[j].x - 1);
            } else
                update(v[j].x);

            j++;
        }

        i=j-1;
    }

    printf( "%d", ans );

    return 0;
}