Cod sursa(job #1874057)

Utilizator GinguIonutGinguIonut GinguIonut Data 9 februarie 2017 17:36:48
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <fstream>
#include <algorithm>
#include <vector>

#define nMax 65000
#define pb push_back
#define mkp make_pair
#define x first
#define y second
#define pii pair<int, int>
#define piiii pair<pii, pii>

using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

int n, nrTarc;
int v[nMax];
pii pct[nMax], vect[nMax];
vector<int> arb[5*nMax];

void mergesort(int node, int st, int dr)
{
    if(st==dr)
    {
        arb[node].pb(pct[st].y);
        return;
    }
    int mid=st+(dr-st)/2;
    mergesort(2*node, st, mid);
    mergesort(2*node+1, mid+1, dr);

    int i=st, j=mid+1, pozLast=st-1;

    for(; i<=mid && j<=dr;)
    {
        if(pct[i].y<=pct[j].y)
        {
            vect[++pozLast]=pct[i];
            i++;
        }
        else
        {
            vect[++pozLast]=pct[j];
            j++;
        }
    }
    for(int ii=i; ii<=mid; ii++)
        vect[++pozLast]=pct[ii];
    for(int jj=j; jj<=dr; jj++)
        vect[++pozLast]=pct[jj];
    for(int i=st; i<=dr; i++)
    {
        arb[node].pb(vect[i].y);
        pct[i]=vect[i];
    }
}

int binSearch1(int node, int st, int dr, int pozst, int pozdr, int pozy)
{
    int pSt=0, pDr=dr-st, Sol=-1;
    while(pSt<=pDr)
    {
        int mid=pSt+(pDr-pSt)/2;
        if(pozy>=arb[node][mid])
        {
            Sol=mid;
            pSt=mid+1;
        }
        else
            pDr=mid-1;
    }
    return Sol;
}

int binSearch0(int node, int st, int dr, int pozst, int pozdr, int pozy)
{
    int pSt=0, pDr=dr-st, Sol=-1;
    while(pSt<=pDr)
    {
        int mid=pSt+(pDr-pSt)/2;
        if(pozy<=arb[node][mid])
        {
            Sol=mid;
            pDr=mid-1;
        }
        else
            pSt=mid+1;
    }
    return Sol;
}

int query(int node, int st, int dr, int pozst, int pozdr, int pozySt, int pozyDr)
{
    int Sol=0;
    if(v[st]>=pozst && v[dr]<=pozdr)
    {
        int sol1=binSearch1(node, st, dr, pozst, pozdr, pozyDr);
        int sol2=binSearch0(node, st, dr, pozst, pozdr, pozySt);
        if(sol1>=sol2 && sol1!=-1 && sol2!=-1)
            Sol+=sol1-sol2+1;
        return Sol;
    }
    if(st==dr)
        return Sol;

    int mid=st+(dr-st)/2;
    if(pozst<=v[mid])
        Sol+=query(2*node, st, mid, pozst, pozdr, pozySt, pozyDr);
    if(pozdr>v[mid])
        Sol+=query(2*node+1, mid+1, dr, pozst, pozdr, pozySt, pozyDr);
    return Sol;
}

int main()
{
    int linS, colS, linF, colF;
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>linS>>colS;
        pct[i]=mkp(linS, colS);
        v[i]=linS;
    }

    sort(pct+1, pct+n+1);
    sort(v+1, v+n+1);
    mergesort(1, 1, n);

    fin>>nrTarc;
    for(int i=1; i<=nrTarc; i++)
    {
        fin>>linS>>colS>>linF>>colF;
        fout<<query(1, 1, n, linS, linF, colS, colF)<<'\n';
    }
}