Cod sursa(job #1536497)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 26 noiembrie 2015 11:32:10
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include<fstream>
#include<vector>
#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];
ifstream fin("zoo.in");
ofstream fout("zoo.out");

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

        int i = 0, j = 0;
        int b = 2 * nod, c = 2 * nod + 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() - 2;
        while(p <= u){
            mid = (p + u) / 2;
            if(v[ a[nod][mid] ].y >= jj1){
                u = mid - 1;
            }
            else{
                p = mid + 1;
            }
        }
        aux = p;

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

int main(){
    fin>> n;
    for(i = 1; i <= n; i++){
        fin>> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1);
    build(1, 1, n);
    for(i = 1; i <= 4 * n; i++){
        a[i].push_back(0);
    }
    fin>> m;
    for(i = 1; i <= m; i++){
        fin>> ii1 >> jj1 >> ii2 >> jj2;
        nr = 0;
        query(1, 1, n, ii1, jj1, ii2, jj2);
        fout<< nr <<"\n";
    }
    return 0;
}