Cod sursa(job #25593)

Utilizator alextheroTandrau Alexandru alexthero Data 4 martie 2007 13:03:36
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <cstdio>
#include <algorithm>

#define nmax 50005
#define mmax 100005
#define vmax 1000005

using namespace std;

int n,m,w,h;
int x[nmax],y[nmax],place[nmax];
int x1[mmax],y1[mmax],place1[mmax];
unsigned short int aib[vmax];

int cmp(int i,int j) {
    if(x[i] < x[j]) return 1;
    else if(x[i] == x[j]) return y[i] < y[j];
    else return 0;
}

int cmp1(int i,int j) {
    if(x1[i] < x1[j]) return 1;
    else if(x1[i] == x1[j]) return y1[i] < y1[j];
    else return 0;
}

int lsb(int x) {
    return x ^ (x - 1) & x;    
}

void update(int x,int val) {
    while(x <= vmax) {
        aib[x] += val;
        x += lsb(x);
    }
}

int suma(int x) {
    int r = 0;
    while(x > 0) {
        r += aib[x];
        x -= lsb(x);
    }
    return r;
}

int sum(int x,int y) {
    return suma(y) - suma(x - 1);
}

int main() {
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);
        
    scanf("%d %d %d %d\n",&n,&m,&w,&h);

    for(int i = 1; i <= n; i++) {
        scanf("%d %d\n",&x[i],&y[i]);
        x[i]++; y[i]++;
        place[i] = i;
    }

    sort(place + 1,place + n + 1,cmp);

    for(int i = 1; i <= m; i++) {
        scanf("%d %d\n",&x1[i],&y1[i]);
        x1[i]++; y1[i]++;
        place1[i] = i;
    }

    sort(place1 + 1,place1 + m + 1,cmp1);
    
    int hambar_stanga = 1,hambar_dreapta = 1,cate = 0;

    for(int i = 1; i <= m; i++) {
        int xc = x1[place1[i]];
        int yc = y1[place1[i]];
  
        while((hambar_stanga <= min(hambar_dreapta,n)) && (x[place[hambar_stanga]] + w < xc)) {
            update(y[place[hambar_stanga]], -1);
            hambar_stanga++;
        }

        while((hambar_dreapta <= n) && (x[place[hambar_dreapta]] <= xc)) {
            update(y[place[hambar_dreapta]],1);
            hambar_dreapta++;
        }

        if(sum(yc - h,yc) >= 1) cate++;
    }

    printf("%d\n",cate);

    return 0;
}