Cod sursa(job #857062)

Utilizator StefanLacheStefan Lache StefanLache Data 17 ianuarie 2013 11:06:58
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int N=16003;
pair <int,int> coordonate[N];
vector <int> arbore[N*10],abscise;
int n,m;
FILE *f=fopen("zoo.in","rt");
FILE *g=fopen("zoo.out","wt");
void construieste(int nod,int st,int dr)
{
        if(st == dr)
        {
            arbore[nod].push_back(coordonate[st].second);
            return ;
        }
        int mij=(st+dr)/2;              //mijlocul intervalului;
        int l=nod *2,r=l+1;            //fiul stang si drept;
        construieste(l,st,mij);             //subarborele stang;
        construieste(r,mij+1,dr);       //subarborele drept;
        arbore[nod].resize(dr-st+1);
        merge(arbore[l].begin(),arbore[l].end(),arbore[r].begin(),arbore[r].end(),arbore[nod].begin());
}
int cautbinar(int nod,int y1, int y2)
{
    return (int)(upper_bound(arbore[nod].begin(),arbore[nod].end(),y2)-lower_bound(arbore[nod].begin(),arbore[nod].end(),y1));
}
int query(int nod,int x,int x1,int x2,int y1,int y2)
{
    int mij=(x1+x2)/2;
    if(x<x1)    return 0;///niciun animal nu are x,abscisa, in cadrul gradinii
    if(x2<=x) return cautbinar(nod,y1,y2);
    return query(2*nod,x,x1,mij,y1,y2)+query(2*nod+1,x,mij+1,x2,y1,y2);
}
int main()
{
        fscanf(f,"%i",&n);
        for(int i=1;i<=n;++i)
            {
                fscanf(f,"%i%i",&coordonate[i].first,&coordonate[i].second);
                abscise.push_back(coordonate[i].first);
            }
        sort(coordonate+1,coordonate+n+1);
        sort(abscise.begin(),abscise.end());
        construieste(1,1,n);            //construim arborele
        fscanf(f,"%i",&m);
        int lim_x1,lim_x2,x1,x2,y1,y2;
        for(int i=1;i<=m;++i)
        {
            fscanf(f,"%i%i%i%i",&x1,&x2,&y1,&y2);
            lim_x1=upper_bound(abscise.begin(),abscise.end(),x1-1)-abscise.begin(); ///returneaza aparitia primului element cu abscisa >=x1;
             lim_x2=upper_bound(abscise.begin(),abscise.end(),x2)-abscise.begin(); ///returneaza aparitia primului element cu abscisa >x2;
             fprintf(f,"%i\n",query(1,lim_x2,1,n,y1,y2)-query(1,lim_x1,1,n,y1,y2));
        }
        return 0;
}