Cod sursa(job #739723)

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

const int N=16005, RSize=4752001, PSize=600005;
int X[N],Y[N],n, DPrint = -1, DRead;
char PRINT[N], READ[N];

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

vector<int> aib[N];

inline bool cifra(char& c)
{
    return '0'<=c && c<='9';
}

void read_int(int& x)
{
    while (!cifra(READ[DRead]))
        DRead++;
    x=0;
    while (cifra(READ[DRead]))
        x = x * 10 + READ[DRead++] - '0';
}

struct Punct
{
    int x,y;

    void get()
    {
        read_int(x);
        read_int(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";
}

void add_to_print(int x)
{
    if (x<10)
    {
        PRINT[++DPrint] = x + '0';
        PRINT[++DPrint] = '\n';
        return;
    }
    add_to_print(x/10);
    PRINT[++DPrint] = x%10 + '0';
}

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

    in.getline(READ,RSize, '\0');

    read_int(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);

    read_int(m);

    while (m--)
    {
        read_int(x);
        read_int(y);
        read_int(z);
        read_int(t);

        x=find(X, x-1);
        y=find(Y, y-1);
        z=find(X, z);
        t=find(Y, t);
        add_to_print(query(z,y,t) - query(x,y,t));
    }
    out<<PRINT;
    return 0;
}