Cod sursa(job #341990)

Utilizator hendrikHendrik Lai hendrik Data 20 august 2009 11:34:37
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define FIN "zoo.in"
#define FOUT "zoo.out"
#define MAX_N 16005
#define x first
#define y second
#define pb push_back
#define INF 2000000005

vector <int> A[MAX_N * 4];
pair <int, int> P[MAX_N];

int N, M, RES;
int x1, x2, y1, y2;

void merge (int nod, int li, int lf){
    int sl = (nod << 1);
    int sr = (nod << 1)|1;
    // santinele
    A[sl].pb(INF), A[sr].pb (INF);
    int i, j, k;
    for (i = 0, j = 0, k = 0; k <= lf - li; ++k){
        if (A[sl][i] < A[sr][j]) {
            A[nod].pb(A[sl][i++]);
        }
        else {
            A[nod].pb(A[sr][j++]);
        }
    }
}

void buildtree (int nod, int li, int lf){
    if (li == lf) A[nod].pb (P[li].y);
    else {
        int m = (li + lf) >> 1;
        buildtree (nod << 1, li, m);
        buildtree ((nod << 1)|1, m + 1, lf);
        
        merge (nod, li, lf);
    }
}

int binar (int nod, int y1, int y2){
    int m, li, lf, cnt_y1, cnt_y2;
    if (A[nod][0] > y2) return 0;
    if (A[nod][A[nod].size() - 1] < y1) return 0;
    
    li = 0, lf = A[nod].size() - 1;
    
    while (li <= lf){
        m = (li + lf) >> 1;
        if (A[nod][m] < y1) li = m + 1;
           else lf = m - 1;
    }
    while (A[nod][m - 1] >= y1 && m) --m;
    while (A[nod][m] < y1 && m < A[nod].size() - 1) ++m;
    cnt_y1 = m;
    
    li = 0, lf = A[nod].size() - 1;
    
    while (li <= lf){
        m = (li + lf) >> 1;
        if (A[nod][m] < y2) li = m + 1;
           else lf = m - 1;
    }
    while (A[nod][m + 1] <= y2 && m < A[nod].size() - 1) ++m;
    while (A[nod][m] > y2 && m) --m;
    cnt_y2 = m;
    
    return cnt_y2 - cnt_y1 + 1;
}

void query (int nod, int li, int lf){
    if (x1 <= P[li].x && P[lf].x <= x2){
        // cautari binare
        RES += binar (nod, y1, y2);
    }
    else if (li != lf){
        int m = (li + lf) >> 1;
        if (x1 <= P[m].x) query (nod << 1, li, m);
        if (P[m + 1].x <= x2) query ((nod << 1)|1, m + 1, lf);
    }
}

int main(){
    int i;
    freopen (FIN, "r", stdin);
    freopen (FOUT, "w", stdout);
    scanf ("%d", &N);
    for (i = 1; i <= N; ++i) scanf ("%d %d", &P[i].x, &P[i].y);
    sort (P + 1, P + N + 1);
    buildtree (1, 1, N);
    scanf ("%d", &M);
    while (M--){
       scanf ("%d %d %d %d", &x1, &y1, &x2, &y2);
       RES = 0;
       query (1, 1, N);
       printf ("%d\n", RES);
    }
    system("pause");
    return 0;
}