Cod sursa(job #935073)

Utilizator rudarelLup Ionut rudarel Data 1 aprilie 2013 14:49:30
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <stdio.h>
#include <algorithm>
 
#define MAXN 32000
#define POW ((st + dr) >> 1)
 
using namespace std;
 
struct NODZ {
    long x, y;
};
 
NODZ P[MAXN];
long n, m, X[MAXN], x1, y1, x2, y2, A[100][MAXN], i;
 
 
//Functia de SORT din stl //cplusplus.com
struct Cmp {
    bool operator () (NODZ a, NODZ b) {
        if (a.x < b.x) return true;
        return false;
    }
};
 
void Build(long lv, long st, long dr) {
    if (st == dr) {
        A[lv][st] = P[st].y;
        return;
    }
    Build(lv + 1, st, POW);
    Build(lv + 1, POW + 1, dr);
    long i = st, j = POW + 1, k = st;
    while (i <= POW || j <= dr)   {
        if ((i <= POW && A[lv + 1][i] < A[lv + 1][j]) || j > dr) {
            A[lv][k++] = A[lv + 1][i++];
        } else {
            A[lv][k++] = A[lv + 1][j++];
        }
    }
}
 
long Search(long *S, long st, long dr, long y) {
    long pmax = st - 1;
    while (st <= dr) {
        if (S[POW] <= y) {
            pmax = POW > pmax ? POW : pmax;
            st = POW + 1;
        } else {
            dr = POW - 1;
        }
    }
    return pmax;
}
 
long Query(long lv, long st, long dr) {
    if (x1 <= st && dr <= x2) {
        if (y1 > A[lv][dr] || y2 < A[lv][st]) {
            return 0;
        }
        if (y1 < A[lv][st] && A[lv][dr] < y2) {
            return (dr - st) + 1;
        }
        long ret = Search(A[lv], st, dr, y2) - Search(A[lv], st, dr, y1 - 1);
        return ret;
    }
    long ret = 0;
    if (x1 <= POW) {
        ret += Query(lv + 1, st, POW);
    }
    if (x2 >  POW) {
        ret += Query(lv + 1, POW + 1, dr);
    }
    return ret;
}
 
int main() {
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    scanf("%ld", &n);
    for (i = 1; i <= n; ++i) {
        scanf("%ld%ld", &P[i].x, &P[i].y);
    }
    sort(P + 1, P + n + 1, Cmp());
    for (i = 1; i <= n; ++i) {
        X[i] = P[i].x;
    }
    Build(1, 1, n);
    scanf("%ld", &m);
    for (i = 1; i <= m; i++) {
        scanf("%ld%ld%ld%ld", &x1, &y1, &x2, &y2);
        if (x2 < X[1] || x1 > X[n]) {
            printf("0\n");
        } else {
            x1 = Search(X, 1, n, x1 - 1) + 1;
            x2 = Search(X, 1, n, x2);
            printf("%ld\n", Query(1, 1, n));
        }
    }
    return 0;
}