Cod sursa(job #2836853)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 21 ianuarie 2022 00:06:21
Problema Ograzi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <set>

using namespace std;

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

int n, m, lung, lat, ans;

struct coords{
    int x, y;
    inline bool operator < (const coords &other) const
    {
        return x < other.x;
    }
}bee[100005];

struct ograda{
    int x, y, tip;
    inline bool operator < (const ograda &other) const
    {
        return x < other.x;
    }
}v[100005];

int main()
{
    fin >> n >> m >> lung >> lat;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[2 * i].x >> v[2 * i].y;
        v[2 * i].tip = -1;
        v[2 * i - 1].x = v[2 * i].x + lung + 1;
        v[2 * i - 1].y = v[2 * i].y;
        v[2 * i - 1].tip = 1;
    }
    for(int i = 1; i <= m; i++)
        fin >> bee[i].x >> bee[i].y;
    sort(v + 1, v + 2 * n + 1);
    sort(bee + 1, bee + m + 1);
    multiset <int> curte;
    int ind = 1;
    for(int i = 1; i <= n; i++)
    {
        while(ind <= 2 * m && v[ind].x <= bee[i].x)
        {
            if(v[ind].tip == -1)
                curte.insert(v[ind].y);
            else
                curte.erase(v[ind].y);
            ind++;
        }
        multiset <int> :: iterator it = curte.lower_bound(bee[i].y);
        if(it != curte.end() && bee[i].y <= *it + lat)
            ans++;
        else if(it != curte.begin())
        {
            --it;
            if(bee[i].y <= *it + lat)
                ans++;
        }
    }
    fout << ans;
    return 0;
}