Cod sursa(job #2068361)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 17 noiembrie 2017 17:31:43
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
pair <int,int> a[16001];
vector <int> v[16001];
int p,sol=0,n;
void build (int nod,int st,int dr){
    int mid,i,j;
    if (st==dr){
        v[nod].push_back(a[p].second);
        p++;
        return;
    }
    mid=(st+dr)/2;
    build (2*nod,st,mid);
    build (2*nod+1,mid+1,dr);
    i=j=0;
    while (i<v[2*nod].size() && j<v[2*nod+1].size()){
        if (v[2*nod][i]<v[2*nod+1][j]){
            v[nod].push_back(v[2*nod][i]);
            i++;
        }
        else {
            v[nod].push_back(v[2*nod+1][j]);
            j++;
        }
    }
    while (i<v[2*nod].size()){
        v[nod].push_back(v[2*nod][i]);
        i++;
    }
    while (j<v[2*nod+1].size()){
        v[nod].push_back(v[2*nod+1][j]);
        j++;
    }
}
int findpoz (int p,int ok){
    int st,dr,mid;
    st=1;
    dr=n;
    while (st<=dr){
        mid=(st+dr)/2;
        if (a[mid].first==p){
            if (ok==0)
                dr=mid-1;
            else st=mid+1;
        }
        else if (a[mid].first<p)
            st=mid+1;
        else dr=mid-1;
    }
    return st;
}
int findp (int nod,int p,int ok){
    int st,dr,mid;
    st=0;
    dr=v[nod].size()-1;
    while (st<=dr){
        mid=(st+dr)/2;
        if (v[nod][mid]==p){
            if (ok==0)
                dr=mid-1;
            else st=mid+1;
        }
        else if (v[nod][mid]<p)
            st=mid+1;
        else dr=mid-1;
    }
    return st;
}
void query (int nod,int st,int dr,int p,int u,int y1,int y2){
    int mid;
    //if (y1==-1000 && y2==0)
      //  printf ("%d %d\n",st,dr);
    if (p<=st && dr<=u){
        /// st...dr intra in componenta
        sol=sol+findp(nod,y2,1)-findp(nod,y1,0);
        return;
    }
    mid=(st+dr)/2;
    if (p<=mid)
        query (2*nod,st,mid,p,u,y1,y2);
    if (mid+1<=u)
        query (2*nod+1,mid+1,dr,p,u,y1,y2);
}
int main()
{
    FILE *fin=fopen ("zoo.in","r");
    FILE *fout=fopen ("zoo.out","w");
    int i,m,x1,y1,x2,y2,prm,u;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d%d",&a[i].first,&a[i].second);
    sort (a+1,a+n+1);
    p=1;
    build (1,1,n);
    fscanf (fin,"%d",&m);
    for (;m;m--){
        fscanf (fin,"%d%d%d%d",&x1,&y1,&x2,&y2);
        if (!(x1<=x2 && y1<=y2)){
            fprintf (fout,"0\n");
            continue;
        }
        prm=findpoz(x1,0);
        u=findpoz(x2,1)-1;
        sol=0;
        query (1,1,n,prm,u,y1,y2);
        fprintf (fout,"%d\n",sol);
    }
    return 0;
}