Cod sursa(job #1134792)

Utilizator mihai995mihai995 mihai995 Data 6 martie 2014 21:40:06
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.63 kb
#include <fstream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#ifndef __builtin_clz
    #define __builtin_clz(X) 18
    #define SHIT 1
#endif

#ifndef SHIT
    #define SHIT 0
#endif

const int N = 16005;

struct Punct{
    int x, y;
};

class Aib{
    struct Node{
        unsigned short int *val, *rank;

        Node(){
            val = rank = NULL;
        }

        void alloc(int n){
            val = (unsigned short int*)malloc( (n + 1) * sizeof(unsigned short int) );
            rank = (unsigned short int*)malloc( (n + 3) * sizeof(unsigned short int) );
            val[0] = 0;
        }

        inline int size(){
            return val[0];
        }

        inline bool isEmpty(){
            return val == NULL;
        }

        void insert(int x){
            val[ ++val[0] ] = x;
        }

        void prepare(Node& N){
            sort(val + 1, val + val[0] + 1);

            if (N.isEmpty())
                return;

            rank[0] = 0;
            for (int i = 1, j = 1 ; i <= val[0] ; i++){
                while (j <= N.size() && N.val[j] <= val[i])
                    j++;
                rank[i] = j - 1;
            }
            rank[ val[0] + 1 ] = rank[ val[0] + 2 ] = N.size();
        }

        int find(int x, int& st, int& dr){
            int ans = st;
            for (int step = 1 << ( 31 - __builtin_clz(dr - st) ) ; step ; step >>= 1)
                if (ans + step <= size() && val[ans + step] <= x)
                    ans += step;
            st = rank[ans];
            dr = rank[ans + 2];
            return ans;
        }
    };
    Node aib[N];
    int size;

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

public:
    void init(int n, int* cnt){
        size = n;

        for (int i = 1 ; i <= n ; i++){
            if (i + step(i) <= n)
                cnt[ i + step(i) ] += cnt[i];
            aib[i].alloc( cnt[i] );
        }
    }

    void insert(int x, int y){
        for (int i = x ; i <= size ; i += step(i))
            aib[i].insert(y);
    }

    void pregen(){
        for (int i = 1 ; i <= size ; i++)
            aib[i].prepare( aib[i - step(i)] );
    }

    int query(int x, int y){
        if (x <= 0 || y <= 0)
            return 0;

        int ans = 0, st = 0, dr = aib[x].size();
        for (int i = x ; i ; i -= step(i))
            ans += aib[i].find(y, st, dr);
        return ans;
    }

    int query(int x, int y, int z, int t){
        return query(z, t) - query(z, y) - query(x, t) + query(x, y);
    }
};

int X[N], Y[N], cnt[N], n;
Punct P[N];
Aib A;

void cleanup(int v[], int n){
    v[0] = 1;

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

int norm(int v[], int x){
    int ans = 0;
    for (int step = 1 << (31 - __builtin_clz( v[0] ) ) ; step ; step >>= 1)
        if ( (ans ^ step) <= v[0] && v[ans ^ step] <= x )
            ans ^= step;
    return ans;
}

void doShit(){
    char bufI[10 * N], bufO[10 * N];
    FILE* in = fopen("zoo.in", "r");
    FILE* out = fopen("zoo.out", "w");

    setvbuf(in, bufI, _IOFBF, 10 * N);
    setvbuf(out, bufO, _IOFBF, 10 * N);

    int x, y, z, t, nrQ;

    fscanf(in, "%d", &n);
    for (int i = 1 ; i <= n ; i++){
        fscanf(in, "%d%d", &P[i].x, &P[i].y);
        X[i] = P[i].x;
        Y[i] = P[i].y;
    }

    cleanup(X, n);
    cleanup(Y, n);

    for (int i = 1 ; i <= n ; i++)
        cnt[ norm(X, P[i].x) ]++;

    A.init(X[0], cnt);
    for (int i = 1 ; i <= n ; i++)
        A.insert( norm(X, P[i].x), norm(Y, P[i].y) );
    A.pregen();

    fscanf(in, "%d", &nrQ);
    while (nrQ--){
        fscanf(in, "%d%d%d%d", &x, &y, &z, &t); x--; y--;
        fprintf(out, "%d\n", A.query( norm(X, x), norm(Y, y), norm(X, z), norm(Y, t) ) );
    }
}

int main(){
    if (SHIT){
        doShit();
        return 0;
    }
    int x, y, z, t, nrQ;

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

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

    cleanup(X, n);
    cleanup(Y, n);

    for (int i = 1 ; i <= n ; i++)
        cnt[ norm(X, P[i].x) ]++;

    A.init(X[0], cnt);
    for (int i = 1 ; i <= n ; i++)
        A.insert( norm(X, P[i].x), norm(Y, P[i].y) );
    A.pregen();

    in >> nrQ;
    while (nrQ--){
        in >> x >> y >> z >> t; x--; y--;
        out << A.query( norm(X, x), norm(Y, y), norm(X, z), norm(Y, t) ) << "\n";
    }

    return 0;
}