Cod sursa(job #2633355)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 7 iulie 2020 12:24:15
Problema Ograzi Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <bits/stdc++.h>

using namespace std;
struct eveniment
{
    int tip,x,y;
};
int n,m,h,w;
const int bsize = (1<<16)+1;
char buffer[bsize];
int p;
int ReadInt()
{
    int nr=0;
    while(!isdigit(buffer[p]))
    {
        if(p==bsize-1)
        {
            p=0;
            fread(buffer,1,bsize,stdin);
        }
        else
            p++;
    }
    while(isdigit(buffer[p]))
    {
        nr=nr*10+buffer[p]-'0';
        if(p==bsize-1)
        {
            p=0;
            fread(buffer,1,bsize,stdin);
        }
        else
            p++;
    }
    return nr;
}
int pri(int x)
{
    if(x==2)
    {
        return 3;
    }
    if(x==1)
    {
        return 2;
    }
    return 1;
}
bool cmp(eveniment a, eveniment b)
{
    return (a.x<b.x || (a.x==b.x && pri(a.tip)>pri(b.tip)));
}
int main()
{
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);
    n=ReadInt();
    m=ReadInt();
    w=ReadInt();
    h=ReadInt();
    vector <eveniment> eves;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        x=ReadInt();
        y=ReadInt();
        eves.push_back(eveniment{2,x,y+h});
        eves.push_back(eveniment{3,x+w,y+h});
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        x=ReadInt();
        y=ReadInt();
        eves.push_back(eveniment{1,x,y});
    }
    int nr=0;
    set <int> s;
    sort(eves.begin(),eves.end(),cmp);
    for(auto e : eves)
    {
        if(e.tip==2)
        {
            s.insert(e.y);
        }
        else if(e.tip==3)
        {
            s.erase(e.y);
        }
        else if(e.tip==1)
        {
            set <int> :: iterator it = s.lower_bound(e.y);
            if(it!=s.end() && *it-e.y<=h)
            {
                ++nr;
            }
        }
    }
    cout<<nr<<'\n';
    return 0;
}