Cod sursa(job #2837006)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 21 ianuarie 2022 14:25:36
Problema Ograzi Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <set>

using namespace std;

ifstream fin("ograzi.in");
ofstream fout("ograzi.out");

const int inf = 0x3f3f3f3f;
int n, m, lung, lat, ans;

struct coords{
    int x, y;
}v[50005], bee[100005];

multiset <int> curte;
multiset <int> :: iterator it;

bool cmp(coords a, coords b)
{
    if(a.y == b.y)
        return a.x <= b.x;
    return a.y < b.y;
}

int main()
{
    fin >> n >> m >> lung >> lat;
    for(int i = 1; i <= n; i++)
        fin >> v[i].x >> v[i].y;
    for(int i = 1; i <= m; i++)
        fin >> bee[i].x >> bee[i].y;
    sort(v + 1, v + n + 1, cmp);
    sort(bee + 1, bee + m + 1, cmp);
    v[n + 1] = {inf, inf};
    bee[m + 1] = {inf, inf};
    int st = 1, dr = 1, b = 1;
    while(b <= m)
    {
        int rez = cmp(v[dr], bee[b]);
        coords a;
        if(rez == 1)
            a = v[dr];
        else
            a = bee[b];
        while(a.y - v[st].y > lat)
        {
            it = curte.lower_bound(v[st].x);
            curte.erase(it);
            st++;
        }
        if(rez == 1)
            curte.insert(v[dr].x), dr++;
        else
        {
            if(!curte.empty())
            {
                if(*curte.begin() > a.x);
                else
                {
                    it = curte.upper_bound(a.x);
                    it--;
                    if(a.x - *it <= lung)
                        ans++;
                }
            }
            b++;
        }
    }
    fout << ans;
    return 0;
}