Cod sursa(job #953067)

Utilizator primulDarie Sergiu primul Data 24 mai 2013 18:42:31
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define pb push_back
#define point pair<int, int>
#define x first
#define y second
#define ls (node << 1)
#define rs ((node << 1) + 1)
#define FOR(i,a,b)\
   for(int i=a; i<=b; ++i)
#define infile "zoo.in"
#define outfile "zoo.out"
#define nMax 16005
using namespace std;
 
struct rectangle{
    int x1, y1, x2, y2;
} Rect;
 
point P[nMax];
 
vector < int > AI[nMax << 2];
 
int N, M;
 
 
void mergeLists(int node){
    unsigned int k = 0, l = 0, r = 0;
 
    AI[node].resize(AI[ls].size() + AI[rs].size());
 
    while(l < AI[ls].size() && r < AI[rs].size())
        if(AI[ls][l] < AI[rs][r])
            AI[node][k++] = AI[ls][l++];
        else
            AI[node][k++] = AI[rs][r++];
 
    while(l < AI[ls].size())
        AI[node][k++] = AI[ls][l++];
 
    while(r < AI[rs].size())
        AI[node][k++] = AI[rs][r++];
}
 
void buildTree(int node, int left, int right){
    if(left == right){
        AI[node].pb(P[left].y);;
        return;
    }
 
    int middle = (left + right) >> 1;
 
    buildTree(ls, left, middle);
    buildTree(rs, middle + 1, right);
 
    mergeLists(node);
}
 
int query(int node, int left, int right){
    if(Rect.x1 <= P[left].x && P[right].x <= Rect.x2)
        return lower_bound(AI[node].begin(), AI[node].end(), Rect.y2 + 1) - lower_bound(AI[node].begin(), AI[node].end(), Rect.y1);
 
    if(left == right)
        return 0;
 
    int res = 0, middle = (left + right) >> 1;
 
    if(Rect.x1 <= P[middle].x)
        res += query(ls, left, middle);
    if(Rect.x2 >= P[middle].x)
        res += query(rs, middle + 1, right);
 
    return res;
}
 
int main(){
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);
 
    scanf("%d", &N);
 
    FOR(i,1,N)
        scanf("%d %d", &P[i].x, &P[i].y);
 
    sort(P + 1, P + N + 1);
 
    buildTree(1, 1, N);
 
    for(scanf("%d", &M); M; M--){
        scanf("%d %d %d %d", &Rect.x1, &Rect.y1, &Rect.x2, &Rect.y2);
 
        Rect.x1 = max(Rect.x1, P[1].x);
        Rect.x2 = min(Rect.x2, P[N].x);
 
        printf("%d\n", query(1, 1, N));
    }
 
    fclose(stdin);
    fclose(stdout);
 
    return 0;
}