Cod sursa(job #1134133)

Utilizator mihai995mihai995 mihai995 Data 6 martie 2014 01:03:27
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 16001;

struct Punct{
    int x, y;

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

class Aib{
    vector<int> aib[N];
    int size;

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

    int find(vector<int>& v, int x){
        if (v.empty() || x < v[0])
            return 0;
        int ans = 0;
        for (int step = 1 << 13 ; step ; step >>= 1)
            if ( (ans ^ step) < v.size() && v[ans ^ step] <= x )
                ans ^= step;
        return ans + 1;
    }

public:
    void init(int n){
        size = n;
    }

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

    int query(int x, int y){
        int ans = 0;
        for (int i = x ; i ; i -= step(i))
            ans += find(aib[i], y);
        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], n;
Punct P[N];
Aib A;

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

int norm(int x){
    int ans = 0;
    for (int step = 1 << 13 ; step ; step >>= 1)
        if ( (ans ^ step) <= X[0] && X[ans ^ step] <= x )
            ans ^= step;
    return ans;
}

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

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

    X[0] = 1;
    X[1] = P[1].x;
    for (int i = 2 ; i <= n ; i++)
        if (P[i].x != X[ X[0] ])
            X[ ++X[0] ] = P[i].x;

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

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

    return 0;
}