Cod sursa(job #1222903)

Utilizator mihai995mihai995 mihai995 Data 24 august 2014 18:24:27
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 1 << 14;

class ArbInt{
    struct Nod{
        int pozSt, pozDr;

        Nod(int pozSt = 0, int pozDr = 0) :
            pozSt(pozSt),
            pozDr(pozDr)
        {}
    };

    vector<Nod> aint[3 * N];
public:
    ArbInt(){
        for (int i = 1 ; i < 3 * N ; i++)
            aint[i].push_back( Nod(0) );
    }

    void update(int x, int y, int poz = 1, int st = 1, int dr = N){
        if (st == dr){
            aint[poz].push_back( Nod() );
            return;
        }
        int m = (st + dr) >> 1;

        if (x <= m)
            update(x, y, poz << 1, st, m);
        else
            update(x, y, 1 + (poz << 1), m + 1, dr);

        aint[poz].push_back( Nod(aint[poz << 1].size() - 1, aint[1 + (poz << 1)].size() - 1) );
    }

    int query(int x, int y, int pMin, int pMax, int poz = 1, int st = 1, int dr = N){
        if (x <= st && dr <= y)
            return pMax - pMin;

        int ans = 0, m = (st + dr) >> 1;

        if (x <= m)
            ans += query(x, y, aint[poz][pMin].pozSt, aint[poz][pMax].pozSt, poz << 1, st, m);
        if (m < y)
            ans += query(x, y, aint[poz][pMin].pozDr, aint[poz][pMax].pozDr, 1 + (poz << 1), m + 1, dr);

        return ans;
    }
};

struct Punct{
    int x, y;

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

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

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

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

void normalize(Punct P[], int n){
    for (int i = 1 ; i <= n ; i++){
        X[i] = P[i].x;
        Y[i] = P[i].y;
    }

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

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

int query(int x, int y, int z, int t){
    return A.query( find(X, x - 1) + 1, find(X, z), find(Y, y - 1), find(Y, t) );
}

int main(){
    ifstream in("zoo.in");
    ofstream out("zoo.out");

    in >> n;
    for (int i = 1 ; i <= n ; i++)
        in >> P[i].x >> P[i].y;
    normalize(P, n);

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

    int nrQ, x, y, z, t;

    in >> nrQ;
    while (nrQ--){
        in >> x >> y >> z >> t;
        out << query(x, y, z, t) << '\n';
    }

    out.close();
    in.close();

    return 0;
}