Cod sursa(job #1000222)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 22 septembrie 2013 14:18:09
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include<stdio.h>
#include<algorithm>

#define NMAX 16007
#define MMAX 100007
#define INF 1000000000

using namespace std;

struct ZOO{
    int x;
    int y;
    bool Tip;
    bool PN;
    int Ind;
} a[NMAX];

int N, Ans[MMAX], n, c[NMAX], m, aib[3 * NMAX], Ap[MMAX];

inline bool cmp(ZOO a, ZOO b){
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

int cb(int val, int st, int dr){
    int med;
    while(st <= dr){
        med = (st + dr) >> 1;
        if(c[med] == val)
            return med;
        if(c[med] < val)
            st = med + 1;
        else
            dr = med - 1;

    }
    if(c[st] == val)
        return st;
    if(c[dr] == val)
        return dr;
    return -1;
}

void Norm(){
    for(int i = 1; i <= n; ++ i)
        c[i] = a[i].y;
    sort(c + 1, c + n + 1);
    for(int i = 1; i <= n; ++ i){
        int poz = cb(a[i].y, 1, n);
        a[i].y = ++ N;
    }
}

void pune(int xx, int yy, int Indd, int ap, int K){
    a[Indd].x = xx;
    a[Indd].y = yy;
    a[Indd].Tip = 1;
    a[Indd].PN = ap;
    a[Indd].Ind = K;
}

void update(int poz, int val, int N){
    while (poz <= N){
        aib[poz] += val;
        poz += poz & (poz ^ (poz - 1));
    }
}
int query(int poz){
    int sol = 0;
    while (poz){
        sol += aib[poz];
        poz -= poz & (poz ^ (poz - 1));
    }
    return sol;
}

int main(){
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
        scanf("%d %d", &a[i].x, &a[i].y);
    scanf("%d", &m);
    for(int i = 1; i <= m; ++ i){
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        pune(x2    , y2    , ++ n, 1, i);
        pune(x2    , y1 - 1, ++ n, 0, i);
        pune(x1 - 1, y1 - 1, ++ n, 1, i);
        pune(x1 - 1, y2    , ++ n, 0, i);
    }
    Norm();
    ///for(int i = 1; i <= n; ++ i)
        ///printf("%d %d\n", a[i].x, a[i].y);
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; ++ i)
        if(a[i].Tip == 0)
            update(a[i].y, 1, N);
        else
            if(a[i].PN == 0)
                Ans[a[i].Ind] -= query(a[i].y);
            else
                Ans[a[i].Ind] += query(a[i].y);
    for(int i = 1; i <= m; ++ i)
        printf("%d\n", Ans[i]);
    return 0;
}