Cod sursa(job #2034738)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 8 octombrie 2017 13:22:20
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<bits/stdc++.h>
#define maxN 16005
using namespace std;
vector<int> A[4*maxN+5];
pair<int,int> v[maxN];
inline void Merge(int x,int y,int z)
{
    int szy=A[y].size();
    int szz=A[z].size();
    int i=0,j=0;
    while(i<szy && j<szz)
    {
        if(A[y][i]<A[z][j]) A[x].push_back(A[y][i++]);
            else A[x].push_back(A[z][j++]);
    }
    while(i<szy) A[x].push_back(A[y][i++]);
    while(j<szz) A[x].push_back(A[z][j++]);
}
inline void Build(int nod,int st,int dr)
{
    if(st==dr)
    {
        A[nod].push_back(v[st].second);
    }
        else
    {
        int mid=(st+dr)>>1;
        Build(2*nod,st,mid);
        Build(2*nod+1,mid+1,dr);
        Merge(nod,2*nod,2*nod+1);
    }
}
int sol=0;
inline void Query(int nod,int st,int dr,int a,int b,int c,int d)
{
    if(a<=v[st].first && v[dr].first<=c)
    {
        vector<int>::iterator y=upper_bound(A[nod].begin(),A[nod].end(),d)-1;
        vector<int>::iterator x=lower_bound(A[nod].begin(),A[nod].end(),b)-1;
        sol=sol+y-x;
       // sol=sol+(upper_bound(A[nod].begin(),A[nod].end(),d)-1)-(lower_bound(A[nod].begin(),A[nod].end(),c));
        return ;
    }
        else
    {
        int mid=(st+dr)>>1;
        if(a<=v[mid].first) Query(2*nod,st,mid,a,b,c,d);
        if(c>=v[mid+1].first) Query(2*nod+1,mid+1,dr,a,b,c,d);
    }
}
int n,q,x,y,xa,ya,xb,yb;
int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        v[i]={x,y};
    }
    sort(v+1,v+n+1);
    Build(1,1,n);
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
        sol=0;
        Query(1,1,n,xa,ya,xb,yb);
        printf("%d\n",sol);
    }
    return 0;
}