Cod sursa(job #933055)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 29 martie 2013 15:58:40
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define NM 16010
#define x first
#define y second

using namespace std;

FILE* fin=fopen("zoo.in","r");
FILE* fout=fopen("zoo.out","w");
const int maxb=1000000;
char buf[maxb];
int ptr=0;

inline int GetInt()
{
    int nr=0, s=1;
    while(buf[ptr]<'0'||'9'<buf[ptr])
    {
        if (buf[ptr]=='-') s=-1;
        if (++ptr>=maxb) fread(buf,1,maxb,fin),ptr=0;
    }

    while ('0'<=buf[ptr]&&buf[ptr]<='9')
    {
        nr=nr*10+buf[ptr]-'0';
        if (++ptr>=maxb) fread(buf,1,maxb,fin),ptr=0;
    }
    return s*nr;
}

typedef pair<int, int> PI;
int N, M;
int P, Val;
int ANS;
PI V[NM];
vector<int> AI[4*NM];
int XMIN, XMAX, YMIN, YMAX;

void Read ()
{
    N=GetInt();
    for (int i=1; i<=N; i++)
    {
        V[i].x=GetInt();
        V[i].y=GetInt();
    }

    sort(V+1, V+N+1);
}

void Insert (int Node, int S, int D)
{
    if (S>=D)
    {
        AI[Node].push_back(Val);
        return;
    }

    int M=(S+D)/2;

    if (P<=M)
        Insert(2*Node, S, M);
    else
        Insert(2*Node+1, M+1, D);
}

void CreateTree (int Node, int S, int D)
{
    if (S>=D)
    {
        AI[Node].push_back(2000000001);
        sort(AI[Node].begin(), AI[Node].end());
        return;
    }

    int M=(S+D)/2;

    CreateTree(2*Node, S, M);
    CreateTree(2*Node+1, M+1, D);

    AI[Node].resize(AI[2*Node].size() + AI[2*Node+1].size());
    merge(AI[2*Node].begin(), AI[2*Node].end(), AI[2*Node+1].begin(), AI[2*Node+1].end(), AI[Node].begin());
}

void Build ()
{
    for (int i=1; i<=N; i++)
    {
        P=i;
        Val=V[i].y;
        Insert(1, 1, N);
    }

    CreateTree(1, 1, N);
}

void Query (int Node, int S, int D)
{
    if (XMIN<=V[S].x && V[D].x<=XMAX)
    {
        ANS+=(upper_bound(AI[Node].begin(), AI[Node].end(), YMAX)) - (lower_bound(AI[Node].begin(), AI[Node].end(), YMIN));
        return;
    }
    if (S>=D) return;

    int M=(S+D)/2;

    if (XMIN<=V[M].x)
        Query(2*Node, S, M);

    if (XMAX>=V[M].x)
        Query(2*Node+1, M+1, D);
}

void Solve ()
{
    M=GetInt();
    for (int i=1; i<=M; i++)
    {
        XMIN=GetInt();
        YMIN=GetInt();
        XMAX=GetInt();
        YMAX=GetInt();

        ANS=0;
        Query(1, 1, N);

        fprintf(fout, "%d\n", ANS);
    }
}

int main ()
{
    Read();
    Build();
    Solve();

    fclose(fin);
    fclose(fout);

    return 0;
}