Cod sursa(job #856288)

Utilizator irene_mFMI Irina Iancu irene_m Data 16 ianuarie 2013 10:32:13
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define fs(x) ((x) * 2)
#define fd(x) ((x) * 2 + 1)

using namespace std;

const char infile[] = "zoo.in";
const char outfile[] = "zoo.out";
const int MAXN = 16002;

struct point {
    int x, y;
};

vector <point> anim;
vector <int> arb[2 * MAXN], animX;
int N, M;

bool cmp(const point& a, const point& b)
{
    if(a.x < b.x)
        return 1;
    if(a.x == b.x) {
        if(a.y < b.y)
            return 1;
        return 0;
    }
    return 0;
}

void update(int nod, int st, int dr){
    if(st == dr) {
        arb[nod].push_back(anim[st - 1].y);
        return;
    }
    int mid = (st + dr) / 2;
    update(fs(nod), st, mid);
    update(fd(nod), mid + 1, dr);
    arb[nod].resize(dr - st + 1);
    merge(arb[fs(nod)].begin(), arb[fs(nod)].end(), arb[fd(nod)].begin(), arb[fd(nod)].end(), arb[nod].begin());
}

int binSearch(vector<int> &v, int y1, int y2)
{
    int st = (int)(lower_bound(v.begin(), v.end(), y1) - v.begin());
    int dr = (int)(upper_bound(v.begin(), v.end(), y2) - v.begin());
    return dr - st;
}

int query(int nod, int st, int dr, int& left, int& right, int& y1, int& y2)
{
    if(right == 0 || left == N + 1)
        return 0;

    if (left <= st && dr <= right)
        return binSearch(arb[nod], y1, y2);

    int mid = (st + dr) / 2, result = 0;

    if (left <= mid)
        result += query(fs(nod), st, mid, left, right, y1, y2);
    if (mid < right)
        result += query(fd(nod), mid + 1, dr, left, right, y1, y2);

    return result;
}

int main()
{
    ifstream fin(infile);
    ofstream fout(outfile);
    fin >> N;

    point z;
    for(int i = 0 ; i < N ; i++)
    {
        fin >> z.x >> z.y;
        anim.push_back(z);
        animX.push_back(z.x);
    }

    sort(anim.begin(), anim.end(), cmp);
    sort(animX.begin(), animX.end());

    update(1, 1, N);
    fin >> M;
    int x1, x2, y1, y2, x1_index, x2_index;
    for(int i = 0 ; i < M ; i++)
    {
        fin >> x1 >> y1 >> x2 >> y2;

        int x1_index = lower_bound(animX.begin(), animX.end(), x1) - animX.begin() + 1;
        int x2_index = upper_bound(animX.begin(), animX.end(), x2) - animX.begin();

        fout << query(1, 1, N, x1_index, x2_index, y1, y2) << "\n";
    }
    return 0;
}