Cod sursa(job #739719)

Utilizator mihai995mihai995 mihai995 Data 23 aprilie 2012 19:37:02
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N=16005;
int X[N],Y[N],n;

vector<int> aib[N];

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

struct Punct
{
    int x,y;

    void get()
    {
        in >> x >> y;
    }

    bool operator<(const Punct& P) const
    {
        return y < P.y;
    }

} Points[N];

int find(int v[],int x)
{
    int i, step = 1<<13;
    for (i = 0 ; step ; step >>= 1)
        if (i + step <= v[0] && v[i+step] <= x)
            i += step;
    return i;
}

int find(vector<int>& v, int x)
{
    int i, step = 1<<13;
    for (i = -1 ; step ; step >>= 1)
        if (i + step < v.size() && v[i+step] <= x)
            i += step;
    return i;
}

inline int step(int& x)
{
    return x & (-x);
}

void update(int x, int val)
{
    for ( ; x<=n ; x += step(x))
        aib[x].push_back(val);
}

int query(int x, int st, int dr)
{
    int rez = 0;
    for ( ; x ; x -= step(x))
        rez += find(aib[x], dr) - find(aib[x], st);
    return rez;
}

void normalise(int v[])
{
    v[0] = 1;
    for (int i = 2 ; i <= n ; i++)
        if (v[i] != v[i-1])
            v[++v[0]]=v[i];
}

void print (int v[])
{
    for (int i = 1 ; i <= v[0] ; i++)
        cout<<v[i]<<" ";
    cout<<"\n";
}

void print (vector<int>& v)
{
    for (vector<int> :: iterator it = v.begin() ; it != v.end() ; it++)
        cout<<(*it)<<" ";
    cout<<"\n";
}

int main()
{
    int m, x, y, z, t;

    in>>n;

    for (int i = 1 ; i <= n ; i++)
    {
        Points[i].get();
        X[i]=Points[i].x;
        Y[i]=Points[i].y;
    }

    sort (X + 1, X + n + 1);
    sort (Y + 1, Y + n + 1);

    normalise(X);
    normalise(Y);

    for (int i = 1 ; i <= n ; i++)
    {
        Points[i].x = find(X, Points[i].x);
        Points[i].y = find(Y, Points[i].y);
    }

    sort (Points + 1, Points + n + 1);

    for (int i = 1 ; i <= n ; i++)
        update(Points[i].x, Points[i].y);

    in>>m;

    while (m--)
    {
        in>>x>>y>>z>>t;
        x=find(X, x-1);
        y=find(Y, y-1);
        z=find(X, z);
        t=find(Y, t);
        out<<query(z,y,t) - query(x,y,t)<<"\n";
    }
    return 0;
}