Cod sursa(job #1536515)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 26 noiembrie 2015 12:18:59
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include<fstream>
#include<vector>
#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
int n, m, ii1, ii2, jj1, jj2, nr, i;
vector<int> a[4 * 16005];
pair<int, int> v[16005];
FILE * fin = fopen("zoo.in", "r");
FILE * fout = fopen("zoo.out", "w");

void build(int nod, int st, int dr){
    if(st == dr){
        a[nod].push_back(st);
    }
    else{
        int mid = ( (st + dr) >> 1);
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);

        int i = 0, j = 0;
        int b = (nod << 1), c = (nod << 1) + 1;
        while(i < a[b].size() && j < a[c].size()){
            if(v[ a[b][i] ].y < v[ a[c][j] ].y){
                a[nod].push_back( a[b][i] );
                i++;
            }
            else{
                a[nod].push_back( a[c][j] );
                j++;
            }
        }
        for(; i < a[b].size(); i++){
            a[nod].push_back( a[b][i] );
        }
        for(; j < a[c].size(); j++){
            a[nod].push_back( a[c][j] );
        }
    }
}

void query(int nod, int st, int dr, int ii1, int jj1, int ii2, int jj2){
    if(ii1 <= v[st].x && v[dr].x <= ii2){
        int p, u, mid, aux;
        p = 0;
        u = a[nod].size() - 1;
        while(p <= u){
            mid = ( (p + u) >> 1);
            if(v[ a[nod][mid] ].y >= jj1){
                u = mid - 1;
            }
            else{
                p = mid + 1;
            }
        }
        aux = p;

        p = 0;
        u = a[nod].size() - 1;
        while(p <= u){
            mid = ( (p + u) >> 1);
            if(v[ a[nod][mid] ].y > jj2){
                u = mid - 1;
            }
            else{
                p = mid + 1;
            }
        }
        nr += (u - aux + 1);
    }
    else{
        int mid = ( (st + dr) >> 1);
        if(ii1 <= v[mid].x){
            query((nod << 1), st, mid, ii1, jj1, ii2, jj2);
        }
        if(ii2 >= v[mid + 1].x){
            query( (nod << 1) + 1, mid + 1, dr, ii1, jj1, ii2, jj2);
        }
    }
}

int main(){
    fscanf(fin, "%d", &n);
    for(i = 1; i <= n; i++){
         fscanf(fin, "%d%d", &v[i].x, &v[i].y);
    }
    sort(v + 1, v + n + 1);
    build(1, 1, n);
    fscanf(fin, "%d", &m);
    for(i = 1; i <= m; i++){
        fscanf(fin, "%d%d%d%d", &ii1, &jj1, &ii2, &jj2);
        nr = 0;
        if(v[1].x > ii2 || v[n].x < ii1){
            fprintf(fout, "0\n");
            continue;
        }
        query(1, 1, n, ii1, jj1, ii2, jj2);
        fprintf(fout, "%d\n", nr);
    }
    return 0;
}