Cod sursa(job #3192685)

Utilizator Dani111Gheorghe Daniel Dani111 Data 13 ianuarie 2024 10:15:30
Problema Ograzi Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int N, M, W, H;
const int MAX = 150000;
const int NMAX = 4 * 1e6 + 5;
const int MMAX = 100005;
unsigned short aint[NMAX];
int k;
int sol;

struct ev{
    int x, y;
    bool type;
}A[MAX + 3];


bool cmp(ev a, ev b) {
    if(a.x < b.x) return true;
    if(a.x == b.x) return a.type <= b.type; //vreau sa am dreptunghiurile inaintea oilor in caz de egalitate
    return false;
}

void update(int nod, int st, int dr, int poz, int val) {
    if(st == dr) {
        aint[nod] = val;
        return;
    }
    
    int mid = (st + dr) / 2;
    if(poz <= mid) {
        update(2 * nod, st, mid, poz, val);
    }
    else {
        update(2 * nod + 1, mid + 1, dr, poz, val);
    }
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

void query(int nod, int st, int dr, int a, int b) {
    if(a <= st && dr <= b) {
        sol += aint[nod];
        return;
    }
    
    if(!sol) {
        int mid = (st + dr) / 2;
        if(a <= mid) {
            query(2 * nod, st, mid, a, b);
        }

        if(b > mid) {
            query(2 * nod + 1, mid + 1, dr, a, b);
        }
    }
}


int main() {
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin >> N >> M >> W >> H;

    //citesc dreptunghiurile
    for(int i = 1; i <= N; i++) {
        int x, y;
        cin >> x >> y;
        A[i].x = x;
        A[i].y = y;
        A[i].type = 0;
    }

    //citesc oile
    for(int i = 1; i <= M; i++) {
        int x, y;
        cin >> x >> y;
        A[N + i].x = x;
        A[N + i].y = y;
        A[N + i].type = 1;
    }

    //sort
    stable_sort(A + 1, A + N + M + 1, cmp);

    queue<pair<int, int>>q;

    //parcuregere baleiere
    for(int i = 1; i <= N + M; i++) {
        //daca s-au terminat dreptunghiuri
        while(!q.empty() && q.front().first < A[i].x) {
            update(1, 1, MMAX, q.front().second, 0);
            q.pop();
        }

        //daca e dreptunghi
        if(A[i].type == 0) {
            update(1, 1, MMAX, A[i].y, 1);
            q.push({A[i].x + W, A[i].y}); // retin locul in care se termina si unde trebuie updatat
        }
        //daca e oaie
        else {  
            sol = 0;
            query(1, 1, MMAX, max(1, A[i].y - H), A[i].y);
            if(sol) k++; 
        }
    }

    cout << k;
}


//sortez dupa x
//point query, range update. Verific daca a inceput un dreptunghi in 
//intervalul [y - H, y]
//daca am ajuns la un eveniment care are x > x al primului dreptunghi din coada, sterg dreptunghiul