Cod sursa(job #1329382)

Utilizator SmarandaMaria Pandele Smaranda Data 29 ianuarie 2015 14:25:21
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.38 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 16003;
int n, c, u, d, a, b, x1, x2, yy1, y2;
int X1 [N], X [N];

struct Point {
    int x, y;
};

struct Elem {
    int st, dr;
};

vector <Point> :: iterator it;

class MyComp {
    public :
        bool operator () (const Point &A, const Point &B) {
            return A.y < B.y;
        }
};

struct AINT {
    vector <Point> v;
    vector <Elem> w;
};

AINT aint [10 * N + 10];

const int SIZE = 32000;

class Myifstream {
    private :
        char buffer [SIZE];
        int cursor;
        FILE *input;
        void advance () {
            ++ cursor;
            if (cursor == SIZE) {
                cursor = 0;
                fread (buffer, 1, SIZE, input);
            }
        }
    public :
        Myifstream (const char *inputName) {
            input = fopen (inputName, "r");
            cursor = 0;
            fread (buffer, 1, SIZE, input);
        }
        Myifstream &operator >> (int &value) {
            int p;
            char semn;
            value = 0;
            while (!(buffer [cursor] >= '0' && buffer [cursor] <= '9')) {
                semn = buffer [cursor];
                advance ();
            }
            if (semn == '-')
                p = -1;
            else p = 1;
            while (buffer [cursor] >= '0' && buffer [cursor] <= '9') {
                value = value * 10 + buffer [cursor] - '0';
                advance ();
            }
            value = value * p;
            return *this;
        }
};
Myifstream fin ("zoo.in");
ofstream fout ("zoo.out");

int binarySearchX (const int &value) {
    int i, step;

    for (i = 0, step = (1 << 19); step; step >>= 1)
        if (i + step <= c && X [i + step] <= value)
            i += step;
    return i;
}

int binarySearchX1 (const int &value) {
    int i, step;

    for (i = 0, step = (1 << 19); step; step >>= 1)
        if (i + step <= c && X [i + step] <= value)
            i += step;
    if (X [i] != value)
        ++ i;
    return i;
}

Point P [N];

void buildtree (int node, int st, int dr) {
    int m, lastst, lastdr;
    Elem temp;

    if (st == dr)
        return;
    m = (st + dr) / 2;
    lastst = lastdr = -1;
    for (it = aint [node].v.begin (); it != aint [node].v.end (); ++ it)
        if ((*it).x <= m) {
            aint [(node << 1)].v.push_back (*it);
            temp.st = aint [(node << 1)].v.size () - 1;
            temp.dr = lastdr;
            lastst = temp.st;
            aint [node].w.push_back (temp);
        }
        else {
            aint [(node << 1) + 1].v.push_back (*it);
            temp.dr = aint [(node << 1) + 1].v.size () - 1;
            temp.st = lastst;
            lastdr = temp.dr;
            aint [node].w.push_back (temp);
        }
    buildtree ((node << 1), st, m);
    buildtree ((node << 1) + 1, m + 1, dr);
}

int query (int node, int st, int dr, int f1, int f2) {
    int m, ans = 0, numst = 0, nf1, nf2;

    if (x1 <= st && dr <= x2) {
        if (f1 == f2 && f1 == -1)
            return 0;
        return 0;
        if (f1 < 0)
            f1 = 0;
        while (f1 < 0 || (f1 >= 0 && f1 < aint [node].v.size () && aint [node].v [f1].y < yy1 )) {
            ++ f1;
            if (f1 >= aint [node].v.size ())
                break;
        }
        if (f1 <= f2)
            return f2 - f1 + 1;
        else return 0;
    }
    m = (st + dr) / 2;
    if (x1 <= m) {
        if (f1 >= 0)
            nf1 = aint [node].w [f1].st;
        else nf1 = -1;
        if (f2 >= 0)
            nf2 = aint [node].w [f2].st;
        else nf2 = -1;
        ans = ans + query ((node << 1), st, m, nf1, nf2);
    }
    if (x2 > m) {
        if (f1 >= 0)
            nf1 = aint [node].w [f1].dr;
        else nf1 = -1;
        if (f2 >= 0)
            nf2 = aint [node].w [f2].dr;
        else nf2 = -1;
        ans = ans + query ((node << 1) + 1, m + 1, dr, nf1, nf2);
    }
    return ans;
}

int main () {
    int i, ans, k, m, f1, f2, st, dr;

    fin >> n;
    for (i = 1; i <= n; i ++) {
        fin >> P [i].x >> P [i].y;
        X1 [++ a] = P [i].x;
    }
    sort (X1 + 1, X1 + a + 1);
    X1 [a + 1] = X1 [a] - 10;
    for (i = 1; i <= a; i ++)
        if (X1 [i] != X1 [i + 1])
            X [++ c] = X1 [i];
    for (i = 1; i <= n; i ++) {
        P [i].x = binarySearchX (P [i].x);
        aint [1].v.push_back (P [i]);
    }
    sort (aint [1].v.begin (), aint [1].v.end (), MyComp ());
    buildtree (1, 1, n);
    fin >> k;
    for (i = 1; i <= k; i ++) {
        fin >> x1 >> yy1 >> x2 >> y2;
        x1 = binarySearchX1 (x1);
        x2 = binarySearchX (x2);

        f1 = f2 = -1;
        st = 0;
        dr = aint [1].v.size () - 1;
        while (st <= dr) {
            m = (st + dr) / 2;
            if (aint [1].v [m].y >= yy1) {
                f1 = m;
                dr = m - 1;
            }
            else
                st = m + 1;
        }
        st = 0;
        dr = aint [1].v.size () - 1;
        while (st <= dr) {
            m = (st + dr) / 2;
            if (aint [1].v [m].y <= y2) {
                f2 = m;
                st = m + 1;
            }
            else dr = m - 1;
        }
        ans = query (1, 1, n, f1, f2);
        fout << ans << "\n";
    }
    return 0;
}