Cod sursa(job #1238421)

Utilizator sebinechitasebi nechita sebinechita Data 6 octombrie 2014 22:19:24
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
#define p pair <int, int>
#define MAX 16002
#define pb push_back
int s=0, n, l, r, v1, v2;
p b[MAX];

vector< p > a[4*MAX];

bool cmp1(p a, p b)
{
    if(a.first==b.first)
        return a.second<b.second;
    return a.first<b.first;
}

void update(int nod, int st, int dr)
{
    int i, j;
    if(st==dr)
    {
        a[nod].pb(b[st]);
        return;
    }
    int mij=(st+dr)>>1;

    update(2*nod, st, mij);
    update(2*nod+1, mij+1, dr);
    i=j=0;
    while(i<a[2*nod].size() && j<a[2*nod+1].size())
    {
        if(a[2*nod][i].second<a[2*nod+1][j].second)
            a[nod].pb(a[2*nod][i++]);
        else
            a[nod].pb(a[2*nod+1][j++]);
    }
    while(i<a[2*nod].size())
    {
        a[nod].pb(a[2*nod][i++]);
    }
    while(j<a[2*nod+1].size())
    {
        a[nod].pb(a[2*nod+1][j++]);
    }
}

int cautbin1(int x)
{
    int step, i;
    for(step=1;step<=n;step<<=1);
    for(i=0;step;step>>=1)
    {
        if(i+step<=n)
        {
            if(b[i+step-1].first<x)
                i+=step;
        }
    }
    return i;
}

int cautbin2(int x)
{
    int step, i;
    for(step=1;step<=n;step<<=1);
    for(i=0;step;step>>=1)
    {
        if(i+step<=n)
        {
            if(b[i+step].first<=x)
                i+=step;
        }
    }
    return i;
}

int cautbin3(vector<p > x, int y)
{
    int step, i, n=x.size();
    for(step=1;step<n;step<<=1);
    for(i=0;step;step>>=1)
    {
        if(i+step<n)
        {
            if(x[i+step-1].second<y)
                i+=step;
        }
    }
    return i;
}

int cautbin4(vector<p > x, int y)
{
    int step, i, n=x.size();
     if(x[0].second>y)
        return -1;
    for(step=1;step<n;step<<=1);
    for(i=0;step;step>>=1)
    {
        if(i+step<n)
        {
            if(x[i+step].second<=y)
                i+=step;
        }
    }
    return i;
}

void query(int nod, int st, int dr)
{

    if(l <= st && dr <= r)
    {
       // cout<<nod<<" "<<st<<" "<<dr<<"\n";
        st=cautbin3(a[nod], v1);
        dr=cautbin4(a[nod], v2);
      //  cout<<a[nod].size()<<"\n";
        for(int i=0;i<a[nod].size();i++)
        {
        //    cout<<a[nod][i].first<<" "<<a[nod][i].second<<"\n";
        }
        //cout<<"\n"<<v1<<" "<<v2<<"\n";
        //cout<<st<<" "<<dr<<"\n";

        if(st<=dr)
        {
            s+=(dr-st)+1;
        }
        return;
    }

    int mij=(st+dr)>>1;
    if(l<=mij)
    {
        query(2*nod, st, mij);
    }
    if(r>=mij+1)
    {

        query(2*nod+1, mij+1, dr);
    }
}

void Q(int st, int dr, int y1, int y2)
{
    l=st;
    r=dr;
    v1=y1;
    v2=y2;
    query(1, 1, n);
}

int main()
{
    int st, dr, nod, i, j, m, x1, y1, y2, x2;
    fin>>n;
    st=1;
    dr=n;
    nod=1;
    while(st<dr)
    {
        nod*=2;
        dr=(st+dr)>>1;
    }

    for(i=1;i<=n;i++)
    {
        p l;
        fin>>l.first>>l.second;
        b[i]=l;
    }
    sort(b+1, b+n+1, cmp1);
    update(1, 1, n);
    fin>>m;
    while(m--)
    {
        s=0;
        b[0]=make_pair(-2000100000, -2000100000);
        fin>>x1>>y1>>x2>>y2;
        st=cautbin1(x1);
        dr=cautbin2(x2);
        Q(st, dr, y1, y2);
        fout<<s<<"\n";
    }

}