Cod sursa(job #7444)

Utilizator alextheroTandrau Alexandru alexthero Data 21 ianuarie 2007 15:45:23
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.44 kb
/*
-> sortez punctele dupa x
-> parcurg de 2 ori intervalele, odata in ordinea x a inceperii intervalului
-> tin cate exista in stanga lui cu y-u intre y1 si y2
-> a doua oara in ordinea x a finalului intervalului
-> tin cate exista in dreapta lui cu y-u intre y1 si y2
-> rezultatul pentru intervalul i va fi query2[i]-query1[i]
*/

#include <stdio.h>
#include <algorithm>
#define nmax 65536
#define mmax 131072

using namespace std;

int x[nmax],y[nmax],px[nmax],py[nmax],pxy[nmax],yr[nmax],n,m;
int x1[nmax],y1[nmax],x2[nmax],y2[nmax],place[nmax];
int aib[nmax],q1[mmax],q2[mmax];

int cmpx(int i,int j) ;
int cmpy(int i,int j) ;
int cmpxy(int i,int j) ;
int cmpx1(int i,int j) ;
int cmpx2(int i,int j) ;
void baga_aib(int x,int val) ;
int suma_aib(int x) ;
int cautamax(int x) ;
int cautamin(int x) ;

int main() {    
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d\n",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d %d\n",&x[i],&y[i]);
        px[i] = i; py[i] = i; pxy[i] = i;
    }
    sort(px + 1,px + n + 1,cmpx);
    sort(py + 1,py + n + 1,cmpy);
    sort(pxy + 1,pxy + n + 1,cmpxy);
    yr[py[1]] = 2;
    for(int i = 2;i <= n;i++) 
        if(y[py[i]] == y[py[i-1]]) yr[py[i]] = yr[py[i-1]];
        else yr[py[i]] = yr[py[i-1]] + 1;
    scanf("%d\n",&m);
    for(int i = 1;i <= m;i++) {
        scanf("%d %d %d %d\n",&x1[i],&y1[i],&x2[i],&y2[i]);
        place[i] = i;
    }
    sort(place + 1,place + m + 1,cmpx1);
    int pi = 0;
    for(int i = 1;i <= m;i++) {
        while((pi < n) && (x[px[pi + 1]] < x1[place[i]])) {
            pi++;
            baga_aib(yr[px[pi]],1);
        }
        int maxy = yr[py[cautamax(y2[place[i]])]];
        int miny = yr[py[cautamin(y1[place[i]])]] - 1;
        q1[place[i]] = suma_aib(maxy) - suma_aib(miny);
    }
    memset(aib,0,sizeof(aib));  
    sort(place + 1,place + m + 1,cmpx2);
    pi = 0;
    for(int i = 1;i <= m;i++) {
        while((pi<n) && (x[px[pi + 1]] <= x2[place[i]])) {
            pi++;
            baga_aib(yr[px[pi]],1);
        }
        int maxy = yr[py[cautamax(y2[place[i]])]];
        int miny = yr[py[cautamin(y1[place[i]])]] - 1;
        q2[place[i]] = suma_aib(maxy) - suma_aib(miny);
    }
    for(int i = 1;i <= m;i++) printf("%d\n",q2[i] - q1[i]);
    return 0;
}

int cmpx(int i,int j) {
    return x[i] >= x[j] ? 0 : 1;
}

int cmpy(int i,int j) {
    return y[i] >= y[j] ? 0 : 1;
}

int cmpxy(int i,int j) {
    return ((x[i] > x[j]) || ((x[i] == x[j]) && (y[i] >= y[j]))) ? 0 : 1;
}

int cmpx1(int i,int j) {
    return x1[i] >= x1[j] ? 0 : 1;
}

int cmpx2(int i,int j) {
    return x2[i] >= x2[j] ? 0 : 1;
}

void baga_aib(int x,int val) {
    while(x < nmax) {
        aib[x] += val;
        x += x ^ (x - 1) & x;
    } 
}

int suma_aib(int x) {   
    int r = 0;
    while(x > 0) {
        r += aib[x];
        x -= x ^ (x - 1) & x;
    }
    return r;
}

int cautamax(int x) {
    int fi = 1,la = n;
    int r = 0;
    while(fi <= la) {
        int mi = (fi + la) / 2;
        if(y[py[mi]] <= x) {
            r = mi;
            fi = mi + 1;
        }
        else la = mi - 1;
    }
    return r;
}

int cautamin(int x) {
    int fi = 1,la = n;
    int r = 0;
    while(fi <= la) {
        int mi = (fi + la) / 2;
        if(y[py[mi]] >= x) {
            r = mi;
            la = mi - 1;
        }
        else fi = mi + 1;
    }
    return r;
}