Cod sursa(job #1239783)

Utilizator sebinechitasebi nechita sebinechita Data 9 octombrie 2014 19:49:39
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.94 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 16010
#define pb push_back
int s=0, n, l, r, v1, v2, st2, dr2;
p b[MAX];

vector< int > a[4*MAX], x;
vector< p > poz[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)
{
    unsigned int i, j;
    if(st==dr)
    {
        a[nod].pb(b[st].second);
        return;
    }
    int mij=(st+dr)>>1;

    update(nod<<1, st, mij);
    update((nod<<1)+1, mij+1, dr);
    i=j=0;
    while(i<a[(nod<<1)].size() && j<a[(nod<<1)+1].size())
    {
        if(a[(nod<<1)][i]<a[(nod<<1)+1][j])
        {
            poz[nod].pb(make_pair(i, j-1));
            a[nod].pb(a[(nod<<1)][i++]);
        }
        else
        {
            poz[nod].pb(make_pair(i-1, j));
            a[nod].pb(a[(nod<<1)+1][j++]);
        }
    }
    while(i<a[(nod<<1)].size())
    {
        poz[nod].pb(make_pair(i, j-1));
        a[nod].pb(a[(nod<<1)][i++]);
    }
    while(j<a[(nod<<1)+1].size())
    {
        poz[nod].pb(make_pair(i-1, j));
        a[nod].pb(a[(nod<<1)+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<int > 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-1<n)
        {
            if(x[i+step-1]<y)
                i+=step;
        }
    }
    return i;
}

int cautbin4(vector<int > 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]<=y)
                i+=step;
        }
    }
    return i;
}

void query(int nod, int st, int dr, int ps, int pf)
{
    if(l <= st && dr <= r)
    {

        if(ps>=0)if(a[nod][ps]<v1)
            ps++;
        if(ps<0)
            ps++;
        if(ps<=pf)
        {
            s+=(pf-ps)+1;
        }
        return;
    }

    int mij=(st+dr)>>1, ps1, pf1;
    if(l<=mij)
    {
        if(ps<0)
        {
            ps1=ps;
        }
        else
        {
            ps1=poz[nod][ps].first;
        }
        if(pf<0)
        {
            pf1=pf;
        }
        else
        {
            pf1=poz[nod][pf].first;
        }
        query((1<<nod), st, mij, ps1, pf1);
    }
    if(r>=mij+1)
    {
        if(ps<0)
        {
            ps1=ps;
        }
        else
        {
            ps1=poz[nod][ps].second;
        }
        if(pf<0)
        {
            pf1=pf;
        }
        else
        {
            pf1=poz[nod][pf].second;
        }
        query((nod<<1)+1, mij+1, dr, ps1, pf1);
    }
}

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

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

int getInt()
{
    int x;
    fin>>x;
    return x;
    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, 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);
    for(i=1;i<=n;i++)
    {
        x.push_back(b[i].first);
    }
    m=getInt();
    while(m--)
    {
        s=0;
        x1=getInt();
        y1=getInt();
        x2=getInt();
        y2=getInt();
        st=lower_bound(x.begin(), x.end(), x1)-x.begin()+1;
        dr=upper_bound(x.begin(), x.end(), x2)-x.begin();
        if(a[1][0]>y2 || a[1][a[1].size()-1]<y1)
        {
            fout<<"0\n";
            continue;
        }
        st2=lower_bound(a[1].begin(), a[1].end(), y1)-a[1].begin();
        dr2=upper_bound(a[1].begin(), a[1].end(), y2)-1-a[1].begin();
        if(st<=dr)
            Q(st, dr, y1, y2);
        fout<<s<<"\n";
    }

}