Cod sursa(job #1760181)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 20 septembrie 2016 14:29:15
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.59 kb
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

ofstream fout( "zoo.out" );

class InputReader{
public:
    InputReader() {}
    InputReader(const char *name) {
        fin = fopen(name, "r");
        buffpos = Size - 1;
    }

    inline InputReader &operator >> (int &n) {
        char x = nextpos();
        while ((x < '0' || x > '9') && x != '-') x = nextpos();
        int semn = 1;
        if (x == '-') {
            semn = -1; x = nextpos();
        }
        n = 0;
        while (x >= '0' && x <= '9') {
            n = n * 10 + x - '0';
            x = nextpos();
        }
        n *= semn;
        return *this;
    }
private:
    static const int Size = (1 << 17);
    FILE *fin;
    int buffpos;
    char buff[ Size ];

    inline char nextpos() {
        ++ buffpos;
        if (buffpos == Size) {
            fread(buff, Size, 1, fin);
            buffpos = 0;
        }
        return buff[ buffpos ];
    }
} fin ("zoo.in");

const int nmax = 16000;
int n, m, n2;

struct pct{
    int x, y;

    inline bool operator < (const pct &a) const {
        return (x < a.x);
    }
} p[nmax + 1];

typedef vector< int > nod;

class Aint{
public:
    nod aint[4 * nmax + 1];

    void build (int nod, int x, int y) {
        if (x == y) {
            aint[ nod ].push_back( p[ x ].y );
            return ;
        }

        int mij = (x + y) / 2;
        build(2 * nod, x, mij);
        build(2 * nod + 1, mij + 1, y);

        aint[ nod ] = uneste(aint[2 * nod], aint[2 * nod + 1]);
    }

    int query (int nod, int x, int y, int st, int dr, int val1, int val2) {
        if (st <= x && y <= dr) {
            int lim1 = lower_bound(aint[ nod ].begin(), aint[ nod ].end(), val1) - aint[ nod ].begin();
            int lim2 = upper_bound(aint[ nod ].begin(), aint[ nod ].end(), val2) - aint[ nod ].begin();
            return lim2 - lim1;
        }

        int mij = (x + y) / 2;
        int ans = 0;
        if (st <= mij) {
            ans += query(2 * nod, x, mij, st, dr, val1, val2);
        }
        if (mij < dr) {
            ans += query(2 * nod + 1, mij + 1, y, st, dr, val1, val2);
        }
        return ans;
    }
private:
    nod uneste (nod a, nod b) {
        int i = 0, j = 0;
        nod sol;
        while (i < (int)a.size() && j < (int)b.size()) {
            if (a[ i ] < b[ j ]) {
                sol.push_back( a[ i ++ ] );
            } else {
                sol.push_back( b[ j ++ ] );
            }
        }
        for (; i < (int)a.size(); ++ i) sol.push_back( a[ i ] );
        for (; j < (int)b.size(); ++ j) sol.push_back( b[ j ] );
        return sol;
    }
} aint;

int bs (int val, int tip) {
    int ans;
    if (tip == 1) {
        ans = n;
        for (int step = n2; step > 0; step >>= 1) {
            if (ans - step > 0 && p[ans - step].x >= val) {
                ans -= step;
            }
        }
    } else {
        ans = 1;
        for (int step = n2; step > 0; step >>= 1) {
            if (ans + step <= n && p[ans + step].x <= val) {
                ans += step;
            }
        }
    }
    return ans;
}
int main() {
    fin >> n;
    for (int i = 1; i <= n; ++ i) {
        fin >> p[ i ].x >> p[ i ].y;
    }
    sort(p + 1, p + n + 1);

    aint.build(1, 1, n);

    for (n2 = 1; (n2 << 1) <= n; n2 <<= 1) {
    }

    fin >> m;
    for (int i = 1; i <= m; ++ i) {
        int x, y, xx, yy;
        fin >> x >> y >> xx >> yy;
        x = bs(x, 1), xx = bs(xx, 0); // pozitiile intre care caut
        if (x > xx) {
            fout << "0\n"; continue;
        }
        fout << aint.query(1, 1, n, x, xx, y, yy) << "\n";
    }

    fout.close();
    return 0;
}