Cod sursa(job #1083233)

Utilizator deneoAdrian Craciun deneo Data 15 ianuarie 2014 19:18:26
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.74 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstdio>

const int MAXN = 16200;

#define For(i, st, dr) for (int (i) = (st); (i) <= (dr); ++(i))
#define BMAX 1000000

int n, m, poz;
char buff[BMAX];
std::vector<int> aint[3 * MAXN], bridge[3 * MAXN][2];
std::pair<int, int> points[MAXN];
std::vector<int> a;

inline void build_my_vector(int nod, int st, int dr) {
    register int stp, drp, n, m;

    stp = drp = 0;
    n = aint[st].size();
    m = aint[dr].size();

    aint[nod].resize(n + m);
    bridge[nod][0].resize(n + m);
    bridge[nod][1].resize(n + m);

    register int pas = 0;

    while (stp < n || drp < m) {
        // stanga
        bridge[nod][0][pas] = stp;
        bridge[nod][1][pas] = drp;
        if (stp != n && (drp == m || aint[dr][drp] > aint[st][stp])) {
            aint[nod][pas] = aint[st][stp];
            ++stp;
        }
        else {
            aint[nod][pas] = aint[dr][drp];
            ++drp;
        }
        ++pas;
    }
}

void build(int nod, int st, int dr) {
    if (st == dr) {
        aint[nod].push_back(points[st].second);
        return;
    }
    int mid = (st + dr) >> 1;
    int stanga = nod << 1;
    int dreapta = (nod << 1) + 1;

    build (stanga, st, mid);
    build (dreapta, mid + 1, dr);

    build_my_vector(nod, stanga, dreapta);

}

void query_aint(int nod, int st, int dr, int &l, int &r, int pozl, int pozr, int &rez) {
    if (pozl > pozr) return;

    if (l <= st && dr <= r) {
        rez += pozr - pozl + 1;
        return;
    }

    int mid = (st + dr) >> 1;

    if (l <= mid) {
        int stanga = nod << 1;
        register int lefty = bridge[nod][0][pozr];
        if (lefty >= aint[stanga].size() || aint[stanga][lefty] > aint[nod][pozr])
            --lefty;
        query_aint(stanga, st, mid, l, r, bridge[nod][0][pozl], lefty, rez);
    }
    if (r > mid) {
        int dreapta = (nod << 1) + 1;
        register int righty = bridge[nod][1][pozr];
        if (righty >= aint[dreapta].size() || aint[dreapta][righty] > aint[nod][pozr])
            --righty;
        query_aint(dreapta, mid + 1, dr, l, r, bridge[nod][1][pozl], righty, rez);
    }
}


inline int query(int x1, int y1, int x2, int y2) {
    int px1 = lower_bound(a.begin(), a.end(), x1) - a.begin() + 1;
    int px2 = upper_bound(a.begin(), a.end(), x2) - a.begin();

    int py1 = lower_bound(aint[1].begin(), aint[1].end(), y1) - aint[1].begin();
    int py2 = upper_bound(aint[1].begin(), aint[1].end(), y2) - aint[1].begin() - 1;

    if (px1 > px2 || py1 > py2) return 0;

    int rez = 0;
    query_aint(1, 1, n, px1, px2, py1, py2, rez);

    return rez;
}

inline int getInt() {
    int val = 0, semn = 1;
    while((buff[poz] < '0' || buff[poz] > '9') && buff[poz] != '-')
        if(++poz == BMAX) fread(buff, 1, BMAX, stdin), poz = 0;
    if(buff[poz] == '-') semn = -1, poz++;
    if(poz == BMAX) fread(buff, 1, BMAX, stdin), poz = 0;
    while(buff[poz] >= '0' && buff[poz] <= '9') {
        val = val * 10 + buff[poz++] - '0';
        if(poz == BMAX) fread(buff, 1, BMAX, stdin), poz = 0;
    } return semn * val;
}

int main() {
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);

    n = getInt();

    For (i, 1, n) {
        points[i].first = getInt();
        points[i].second = getInt();
        a.push_back(points[i].first);
    }

    sort(points + 1, points + n + 1);
    sort(a.begin(), a.end());

    build(1, 1, n);

    m = getInt();

    For(i, 1, m) {
        int x1, y1, x2, y2;
        x1 = getInt();
        y1 = getInt();
        x2 = getInt();
        y2 = getInt();
        printf("%d\n", query(x1, y1, x2, y2));
    }

    return 0;
}