Cod sursa(job #219430)

Utilizator CezarMocanCezar Mocan CezarMocan Data 6 noiembrie 2008 21:52:39
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <cstdio>
#include <algorithm>
#include <set>

using namespace std;

struct punct {
    int x, y, z;    
};

int x[20100], t[20100], tt[20100], aib[20000], sol[150000];
punct v[450000], p1, p2, p3, p4;
int i, j, n, m, a, b, c, d, poz, nn, r, cb;

bool cmp2(punct a, punct b) {
    if ((a.x < b.x) || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.z < b.z))
        return true;
    else
        return false;
}

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

void update(int a, int b) {
    while (a <= nn) {
        aib[a] += b;
        a += lsb(a);    
    }
}

int query(int a) {
    int rez = 0;
    if (a <= 0)
        return 0;
    while (a > 0) {
        rez += aib[a];
        a -= lsb(a);    
    }    
    return rez;
}

int caut_bin(int l, int r) {
    int m = (l + r) / 2;
       
    if (t[m] <= cb && t[m+1] > cb) 
        return m;    
    
    if (cb < t[m])
        return caut_bin(l, m-1);
    else
        return caut_bin(m+1, r);
}

int main(){
    
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    
    scanf("%d", &n);
    nn = n;
    for (i = 1; i <= n; i++) { 
        scanf("%d%d", &a, &b);
        v[i].x = a;
        v[i].y = b;
        t[i] = v[i].y;
    }
    
    sort(t+1, t+n+1);
    
    i = 1;
    nn = 0;
    
    while (i <= n) {
        nn++;
        tt[nn] = t[i];
        j = i;
        while (t[j] == t[i])
            j++;
        i = j;
    }
    
    memset(t, 0, sizeof(t));
    for (i = 1; i <= nn; i++)
        t[i] = tt[i];
    t[nn+1] = 1000000000;
    t[0] = -1000000000;
    
    scanf("%d", &m);
    
    for (i=1; i<=m; i++) {
        scanf("%d%d%d%d", &p1.x, &p1.y, &p2.x, &p2.y);
        p1.x--;
        p1.y--;
        p3.x = p1.x;
        p3.y = p2.y-1;
        p4.x = p2.x-1;
        p4.y = p1.y;
        p1.z = p2.z = i * 10;   
        p3.z = p4.z = i * 10 + 1;
        v[n + 1] = p1;
        v[n + 2] = p2;
        v[n + 3] = p3;
        v[n + 4] = p4;
        n += 4;
    }
    
    sort(v + 1, v + n + 1, cmp2);
    
    for (i = 1; i <= n; i++) {
        if (v[i].z == 0) {
            cb = v[i].y;
            poz = caut_bin(0, nn);
            if (poz > 0)
                update(poz, 1);    
        }
        else {
            cb = v[i].y;
            poz = caut_bin(0, nn);
            r = query(poz);
            if (v[i].z % 10 == 0) 
                sol[v[i].z/10] += r;
            else 
                sol[v[i].z/10] -= r;
        }    
    }
        
    for (i = 1; i <= m; i++)
        printf("%d\n", sol[i]);

    return 0;
}