Cod sursa(job #175907)

Utilizator DorinOltean Dorin Dorin Data 10 aprilie 2008 16:27:00
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
# include <fstream>

# define MAX 32001

# define m ((st+dr)>>1)

using namespace std;

int n, X[MAX], x1, x2, y1, y2;
int T[15][MAX];
struct Punct{
    int x, y;
} p[MAX];

struct Cmp{
    bool operator () (Punct a, Punct b)
    {
        return (a.x < b.x);
    }
};

int Search(int a[], int l, int r, int v)
{
    int i, step;
    
	for (step = 1; step <= (r-l)+1; step <<= 1);
    
    for (i = l-1; step; step >>= 1)   
        if (i + step <= r && a[i+step] <= v)
            i += step;
    
    return i; 
}

void Build(int lv, int st, int dr)
{
    if (st == dr)
    {
        T[lv][st] = p[st].y;
        return;
    }      
    
    Build(lv + 1, st,  m);
    Build(lv + 1, m+1, dr);
    
    int i, j, k;
    
    for (i = st, j = m+1, k = st; i <= m || j <= dr; )
        if (j > dr || (i <= m && T[lv+1][i] < T[lv+1][j]))
            T[lv][k++] = T[lv+1][i++];
        else 
            T[lv][k++] = T[lv+1][j++];
}       

int Query(int lv, int st, int dr)
{
    if (x1 <= st && dr <= x2)    
    {
        if (y2 < T[lv][st] || y1 > T[lv][dr]) 
            return 0;       
        if (y1 < T[lv][st] && y2 > T[lv][dr])
            return (dr-st)+1;
        return Search(T[lv], st, dr, y2) - 
               Search(T[lv], st, dr, y1-1);
    }
    
    int t = 0;
    
    if (x1 <= m) t += Query(lv + 1, st,  m);
    if (m < x2)  t += Query(lv + 1, m+1, dr);
    
    return t;
}

int main()
{
    int i, q;
    
    ifstream fin("zoo.in");
    ofstream fout("zoo.out");
    
    fin >> n;
    for (i = 1; i <= n; i++)    
        fin >> p[i].x >> p[i].y;
    
    sort(p+1, p+n+1, Cmp());
	
	for (i = 1; i <= n; i++) X[i] = p[i].x;
	
    Build(1, 1, n);
    
    fin >> q;
    for (; q >= 1; q--)
    {
         fin >> x1 >> y1 >> x2 >> y2; 
         if (x2 < X[1] || x1 > X[n]) fout << "0\n";
         else
         {
             x1 = Search(X, 1, n, x1-1) + 1;
             x2 = Search(X, 1, n, x2);
             fout << Query(1, 1, n) << "\n";    
         } 
    }
    
    fin.close();
    fout.close();
    
    return 0;
}