Cod sursa(job #828751)

Utilizator pantaniMarco Pantani pantani Data 4 decembrie 2012 12:54:59
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <cstdio>

#include <iostream>
#include <vector>
#include <algorithm>
 
#define NMax 16005
 
using namespace std;
 
typedef struct
{
    int X, Y;
}
Coord;
 
vector <int> AI[4*NMax];
Coord Animals[NMax];
int N;
 
inline bool cmp (Coord A, Coord B)
{
    if (A.X<B.X)
    {
        return true;
    }
    if (A.X>B.X)
    {
        return false;
    }
    if (A.Y<B.Y)
    {
        return true;
    }
    return false;
}
 
void BuildTree (int K, int L, int R)
{
    int Mid=(L+R)/2;
    if (L==R)
    {
        AI[K].resize (1, Animals[Mid].Y);
        return;
    }
    BuildTree (2*K, L, Mid);
    BuildTree (2*K+1, Mid+1, R);
    AI[K].resize (AI[2*K].size ()+AI[2*K+1].size ());
    merge (AI[2*K].begin (), AI[2*K].end (), AI[2*K+1].begin (), AI[2*K+1].end (), AI[K].begin ());
}
 
int Query (int K, int L, int R, int QX1, int QX2, int QY1, int QY2)
{
    int Mid=(L+R)/2;
    if (QX1<=Animals[L].X and Animals[R].X<=QX2)
    {
        return lower_bound (AI[K].begin (), AI[K].end (), QY2+1)-lower_bound (AI[K].begin (), AI[K].end (), QY1);
    }
    if (L==R)
    {
        return 0;
    }
    if (QX2<Animals[Mid+1].X)
    {
        return Query (2*K, L, Mid, QX1, QX2, QY1, QY2);
    }
    if (QX1>Animals[Mid].X)
    {
        return Query (2*K+1, Mid+1, R, QX1, QX2, QY1, QY2);
    }
    return Query (2*K, L, Mid, QX1, Animals[Mid].X, QY1, QY2)+Query (2*K+1, Mid+1, R, Animals[Mid+1].X, QX2, QY1, QY2);
}
 
int main()
{
    freopen ("zoo.in", "r", stdin);
    freopen ("zoo.out", "w", stdout);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%d %d", &Animals[i].X, &Animals[i].Y);
    }
    sort (Animals+1, Animals+N+1, cmp);
    BuildTree (1, 1, N);
    int M;
    scanf ("%d", &M);
    for (; M>0; --M)
    {
        int QX1, QX2, QY1, QY2;
        scanf ("%d %d %d %d", &QX1, &QY1, &QX2, &QY2);
        QX1=max (QX1, Animals[1].X);
        QX2=min (QX2, Animals[N].X);
        printf ("%d\n", Query (1, 1, N, QX1, QX2, QY1, QY2));
    }
    return 0;
}