Cod sursa(job #1546876)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 8 decembrie 2015 20:02:28
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAXN 16000
#define x first
#define y second
#define PUT 14
using namespace std;

typedef pair <int, int> punct;
typedef vector <punct> lst;
vector <int> Aint[(5 * MAXN) + 1];
lst v;
int n, m;

void buildT(int node, int l, int r) {
    if (l == r)
        Aint[node].push_back(l);
    else {
        int mid = (l + r) >> 1;
        int left_son = node * 2, right_son = (node * 2) + 1;
        buildT(left_son, l, mid);
        buildT(right_son, mid + 1, r);

        //Aint[node] = interclasare
        int p1 = 0, p2 = 0;
        while (p1 < Aint[left_son].size() && p2 < Aint[right_son].size()) {
            int pl1 = 0, pl2 = 1;
            int P = Aint[right_son][p2];
            if (v[Aint[left_son][p1]].y < v[Aint[right_son][p2]].y) {
                P = Aint[left_son][p1];
                pl1 = 1;
                pl2 = 0;
            }

            Aint[node].push_back(P);
            p1 += pl1;
            p2 += pl2;
        }

        while (p1 < Aint[left_son].size())
            Aint[node].push_back(Aint[left_son][p1++]);
        while (p2 < Aint[right_son].size())
            Aint[node].push_back(Aint[right_son][p2++]);

    }
}

inline int binsearch1(int node, int val) {
    int sol = 0, pas = (1 << 14);
    while (pas) {
        int pos = sol + pas;
        //if (pos <Aint[node].size())
            //cerr<<Aint[node][pos].x<<" "<<Aint[node][pos].y<<"\n";
        if (pos < Aint[node].size() && v[Aint[node][pos]].y < val)
            sol = pos;
        pas >>= 1;
    }

    if (v[Aint[node][sol]].y < val)
        ++sol;
    if (sol >= Aint[node].size())
        return -1;
    if (v[Aint[node][sol]].y < val)
        return -1;
    return sol;
}

inline int binsearch2(int node, int val) {
    int sol = 0, pas = (1 << 14);

    while (pas) {
        int pos = sol +  pas;
        if (pos < Aint[node].size() && v[Aint[node][pos]].y <= val)
            sol = pos;
        pas >>= 1;
    }

    if (v[Aint[node][sol]].y <= val)
        ++sol;
    if (sol >= Aint[node].size())
        return -1;
    if (v[Aint[node][sol]].y <= val)
        return -1;
    return sol;
}

inline int cauta(int node, punct P1, punct P2) {
    int pos1 = binsearch1(node, P1.y), pos2 = binsearch2(node, P2.y); //prima pos >= si prima pos mai mare.

    if (pos1 == -1)
        return 0;
    if (pos2 == 0)
        return 0;
    if (pos2 == -1) {
        pos2 = Aint[node].size() - 1;
    }
    else
        --pos2;

    return pos2 - pos1 + 1;
}

int Query(int node, int l, int r, punct P1, punct P2) {
    if (v[r].x < P1.x || v[l].x > P2.x)
        return 0;
    if (v[l].x >= P1.x && v[r].x <= P2.y)
        return cauta(node, P1, P2);

    int mid = (l + r) >> 1;
    int left_son = node * 2, right_son = (node * 2) + 1;
    return Query(left_son, l, mid, P1, P2) + Query(right_son, mid + 1, r, P1, P2);
}

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

    cin >> n;
    for (int i = 0 ; i < n ; ++i) {
        punct pc;
        cin >> pc.x >> pc.y;
        v.push_back(pc);
    }

    sort(v.begin(), v.end());

    buildT(1, 0, n - 1);

    cin >> m;

    for (int i = 0 ; i < m ; ++i) {
        punct P1, P2;
        cin >> P1.x >> P1.y >> P2.x >> P2.y;

        cout << Query(1, 0, n - 1, P1, P2) << "\n";
    }

    return 0;
}