Cod sursa(job #1238833)

Utilizator sebinechitasebi nechita sebinechita Data 7 octombrie 2014 20:20:21
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.79 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;
    if(b[n].first<x)
        return n+1;
    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;
    if(x<b[1].first)
        return 0;
    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();
    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)
    {
        if(a[nod][0].second>v2 || a[nod][a[nod].size()-1].second<v1)
            return;
        st=cautbin3(a[nod], v1);
        dr=cautbin4(a[nod], v2);

        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);
}

unsigned const maxb=8192;
char buf[maxb];
unsigned ptr=maxb-1;

int getInt()
{
    int rez=0, s=1;
    while(!((buf[ptr]>='0' && buf[ptr]<='9') || buf[ptr]=='-'))
    {
        if(++ptr>=maxb)
            fin.read(buf, maxb), ptr=0;
    }
    if(buf[ptr]=='-')
    {
        s=-1;
        if(++ptr>=maxb)
            fin.read(buf, maxb), ptr=0;
    }
    while((buf[ptr]>='0' && buf[ptr]<='9'))
    {
        rez=rez*10+buf[ptr]-'0';
        if(++ptr>=maxb)
            fin.read(buf, maxb), ptr=0;
    }
    return rez*s;
}

int main()
{
    int st, dr, nod, i, j, m, x1, y1, y2, x2;
    n=getInt();
    for(i=1;i<=n;i++)
        {
            b[i].first=getInt();
            b[i].second=getInt();
        }
    sort(b+1, b+n+1, cmp1);
    update(1, 1, n);

    m=getInt();
    while(m--)
    {
        s=0;
        b[0]=make_pair(-2000100000, -2000100000);
        x1=getInt();
        y1=getInt();
        x2=getInt();
        y2=getInt();
        st=cautbin1(x1);
        dr=cautbin2(x2);

        if(st<=dr)
            Q(st, dr, y1, y2);
        fout<<s<<"\n";
    }

}