Cod sursa(job #949309)

Utilizator misinozzz zzz misino Data 13 mai 2013 11:31:52
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define punct pair<int,int>
#define x first
#define y second
#define pb push_back
#define lb lower_bound
#define dreptunghi pair<pair<int,int>,pair<int,int> >
#define x1 first.first
#define x2 first.second
#define y1 second.first
#define y2 second.second
#define b begin
#define e end
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int i,m,n;
punct p[16010];
dreptunghi d;
vector<int>v[50010];
void interclasare(int nod)
{
    v[nod].resize(v[nod<<1].size()+v[(nod<<1)+1].size());
    int i=0,j=0,k=0;
    while(i<v[nod<<1].size()&&j<v[(nod<<1)+1].size())
    {
        if(v[nod<<1][i]<v[(nod<<1)+1][j])
        {
            v[nod][k]=v[nod<<1][i];
            ++k;
            ++i;
        }
        else
        {
            v[nod][k]=v[(nod<<1)+1][j];
            ++k;
            ++j;
        }
    }
    while(i<v[nod<<1].size())
    {
        v[nod][k]=v[nod<<1][i];
        ++k;
        ++i;
    }
    while(j<v[(nod<<1)+1].size())
    {
        v[nod][k]=v[(nod<<1)+1][j];
        ++k;
        ++j;
    }
}
void update(int nod,int li,int ls)
{
    if(li==ls)
    {
        v[nod].pb(p[li].y);
        return;
    }
    int mij=(li+ls)>>1;
    update(nod<<1,li,mij);
    update((nod<<1)+1,mij+1,ls);
    interclasare(nod);
}
int query(int nod,int li,int ls)
{
    if(d.x1<=p[li].x&&d.x2>=p[ls].x)
    {
        return lb(v[nod].b(),v[nod].e(),d.y2+1)-lb(v[nod].b(),v[nod].e(),d.y1);
    }
    if(li==ls)
    return 0;
    int mij=(li+ls)>>1,sol=0;
    if(d.x1<=p[mij].x)
    sol+=query(nod<<1,li,mij);
    if(d.x2>=p[mij+1].x)
    sol+=query((nod<<1)+1,mij+1,ls);
    return sol;
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    f>>p[i].x>>p[i].y;
    sort(p+1,p+n+1);
    update(1,1,n);
    for(f>>m;m;--m)
    {
        f>>d.x1>>d.y1>>d.x2>>d.y2;
        d.x1=max(d.x1,p[1].x);
        d.x2=min(d.x2,p[n].x);
        g<<query(1,1,n)<<'\n';
    }
    return 0;
}