Cod sursa(job #2628810)

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

FILE *fin;
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 current = 2047;
char buffer[2048];
char getChar (){
    current ++;
    if (current == 2048){
        current = 0;

        fread (buffer, 1, 2048, fin);
    }
    return buffer[current];
}

void read(int &number){
    char chr = getChar();
    number = 0;
    while ('0' <= chr and chr <= '9'){
        number = number * 10 + (chr - '0');
        chr = getChar();
    }
}

std::vector <int> Xs;

int main()
{
    fin = fopen("ograzi.in", "r");
    int S, A, i, lx, ly, ans=0;
    read (A); read(S); read(lx); read(ly);

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

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

    std::sort (Xs.begin(), Xs.end());

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

    int a=0, s=0, X;
    for (i=0; i<Xs.size(); i++){
        if (i > 0 and Xs[i] == Xs[i-1])
            continue;
        X = Xs[i];
        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;
}