Cod sursa(job #2628802)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 17 iunie 2020 16:26:45
Problema Ograzi Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
#define maxn 100005

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

struct point{
    int x, y;
}sheep[maxn], area[maxn];

bool pointSort (point a, point b){
    return a.x < b.x;
}

int main()
{
    int S, A, i, lx, ly, ans=0;
    fin >> A >> S >> lx >> ly;

    for (i=0; i<A; i++){
        fin >> area[i].x;
        fin >> area[i].y;
    }
    std::sort (area, area+A, pointSort);

    for (i=0; i<S; i++){
        fin >> sheep[i].x;
        fin >> sheep[i].y;
    }
    std::sort (sheep, sheep+S, pointSort);

    std::set <int> set;
    std::deque <std::pair <int, int>> dq;

    int a, s, X;
    for (X=0, a=0, s=0; X<=1e6; X++){
        while (dq.empty() == false and dq.front().first < X-lx){
            set.erase (dq.front().second);
            dq.pop_front();
        }
        for (; a<A and area[a].x == X; a++){
            set.insert (area[a].y);
            dq.push_back ({area[a].x, area[a].y});
        }
        for (; s<S and sheep[s].x == X; s++){
            if (set.empty() == true)
                continue;
            auto it = set.upper_bound(sheep[s].y);
            it --;
            int pos = *it;
            if (sheep[s].y - ly <= pos and pos <= sheep[s].y)
                ans ++;
        }
    }

    fout << ans << '\n';

    return 0;
}