Cod sursa(job #25917)

Utilizator alextheroTandrau Alexandru alexthero Data 4 martie 2007 16:14:33
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 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];
char s[16];

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++) {
        gets(s);
        int l = strlen(s),ind = 0,a = 0,b = 0;     
        while (s[ind] <= '9' && s[ind] >= '0') {
            a = a * 10 + s[ind] - '0';
            ++ind;
        }
        while (!(s[ind] <= '9' && s[ind] >= '0')) ++ind;
        while (ind < l && '0' <= s[ind] && s[ind] <= '9') {
            b = b * 10 + s[ind] - '0';
            ++ind;
        }
        x[i] = a; y[i] = b;
        x[i]++; y[i]++;
        place[i] = i;
    }

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

    for(int i = 1; i <= m; i++) {
        gets(s);
        int l = strlen(s),ind = 0,a = 0,b = 0;
        while (s[ind] <= '9' && s[ind] >= '0') {
            a = a * 10 + s[ind] - '0';
            ++ind;
        }
        while (!(s[ind] <= '9' && s[ind] >= '0')) ++ind;
        while (ind < l && '0' <= s[ind] && s[ind] <= '9') {
            b = b * 10 + s[ind] - '0';
            ++ind;
        }
        x1[i] = a; y1[i] = b;
        place1[i] = i;
        x1[i]++; y1[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 < hambar_dreapta - 1) && (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;
}