Cod sursa(job #2064497)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 12 noiembrie 2017 14:12:53
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define DIM 20002
#define INF 2000000010

using namespace std;

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

int n, X1, X2, Y1, Y2, m, s;

struct animal{
    int x, y;
}a[DIM], animalinfinit;

vector<animal> aint[6 * DIM];

bool cmpx(animal a, animal b){
    return a.x < b.x;
}

bool cmpy(animal a, animal b){
    return a.y < b.y;
}

void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].push_back(a[st]);
        aint[nod].push_back(animalinfinit);
        return;
    }
    for(int i = st; i <= dr; ++ i)
        aint[nod].push_back(a[i]);
    sort(aint[nod].begin(), aint[nod].end(), cmpy);
    aint[nod].push_back(animalinfinit);
    int mid = (st + dr) / 2;
    build(2 * nod, st, mid);
    build(2 * nod + 1, mid + 1, dr);
}


/*int caut1a(int nod, int val){
    int st = 0;
    int dr = aint[nod].size() - 1;
    while(st <= dr){
        int mid = (st + dr) / 2;
        if(aint[nod][mid].y < val)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return st;
}

int caut2a(int nod, int val){
    int st = 0;
    int dr = aint[nod].size() - 1;
    while(st <= dr){
        int mid = (st + dr) / 2;
        if(aint[nod][mid].y <= val)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return dr;
}*/

void query(int nod, int st, int dr, int X1, int X2, int Y1, int Y2){
    if(X1 <= st && X2 >= dr){
        animal aux1, aux2;
        aux1.x = a[X1].x;
        aux1.y = Y1;
        aux2.x = a[X2].x;
        aux2.y = Y2;
        s += (int)(upper_bound(aint[nod].begin(), aint[nod].end(), aux2, cmpy) - lower_bound(aint[nod].begin(), aint[nod].end(), aux1, cmpy));
        //s -= caut1a(nod, Y1);
        //s += caut2a(nod, Y2);
        //++ s;
        return;
    }
    int mid = (st + dr) / 2;
    if(X1 <= mid)
        query(2 * nod, st, mid, X1, X2, Y1, Y2);
    if(X2 > mid)
        query(2 * nod + 1, mid + 1, dr, X1, X2, Y1, Y2);
}

int caut1(int val){
    int st = 1;
    int dr = n;
    while(st <= dr){
        int mid = (st + dr) / 2;
        if(a[mid].x < val)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return st;
}

int caut2(int val){
    int st = 1;
    int dr = n;
    while(st <= dr){
        int mid = (st + dr) / 2;
        if(a[mid].x <= val)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return dr;
}


int main()
{
    f>>n;
    for(int i = 1; i <= n; ++ i)
        f>>a[i].x>>a[i].y;

    sort(a + 1, a + n + 1, cmpx);

    animalinfinit.y = INF;

    build(1, 1, n);

    f>>m;

    for(int i = 1; i <= m; ++ i){
        f>>X1>>Y1>>X2>>Y2;
        X1 = caut1(X1);
        X2 = caut2(X2);
        s = 0;
        query(1, 1, n, X1, X2, Y1, Y2);
        g<<s<<'\n';
    }
    return 0;
}