Cod sursa(job #2238356)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 5 septembrie 2018 12:51:29
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define DIM 16010
using namespace std;

ifstream fin ("zoo.in");
ofstream fout ("zoo.out");
int n,m,i,X,Y,X2,Y2,sol;
vector <int> a[4*DIM];
pair <int,int> v[DIM];
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);

        /// interclasam ca sa le avem acum sortate dupa y
        int i = 0, j = 0;
        int x = 2*nod, y = 2*nod+1;
        while (i < a[x].size() && j < a[y].size()){
            if (v[a[x][i]].second < v[a[y][j]].second){
                a[nod].push_back (a[x][i]);
                i++;
            }
            else{
                a[nod].push_back (a[y][j]);
                j++;
            }
        }
        for (;i<a[x].size();i++)
            a[nod].push_back (a[x][i]);
        for (;j<a[y].size();j++)
            a[nod].push_back (a[y][j]);
    }
}
void query (int nod,int st,int dr,int X,int Y,int X2,int Y2){
    if (v[st].first >= X && v[dr].first <= X2){
        /// cautam binar ambele capetem (Y si Y2)
        int p = 0;
        int u = a[nod].size()-1;
        while (p <= u){
            int mid = (p+u)/2;
            if (v[a[nod][mid]].second < Y)
                p = mid + 1;
            else u = mid - 1;
        }

        int poz = p;
        p = 0, u = a[nod].size() - 1;
        while (p <= u){
            int mid = (p+u)/2;
            if (v[a[nod][mid]].second <= Y2)
                p = mid+1;
            else  u = mid-1;
        }

        sol += (u-poz+1);

    }
    else{

        int mid = (st+dr)/2;
        if (X <= v[mid].first)
            query (2*nod,st,mid,X,Y,X2,Y2);
        if (v[mid+1].first <= X2)
            query (2*nod+1,mid+1,dr,X,Y,X2,Y2);
    }

}
int main (){

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].first>>v[i].second;

    sort (v+1,v+n+1); /// sortam dupa x
    build (1,1,n);

    fin>>m;
    for (;m--;){
        fin>>X>>Y>>X2>>Y2;
        if (v[1].first > X2 || X > v[n].first){
            fout<<"0\n";
            continue;
        }
        sol = 0;
        query (1,1,n,X,Y,X2,Y2);
        fout<<sol<<"\n";
    }


    return 0;
}