Cod sursa(job #1083196)

Utilizator deneoAdrian Craciun deneo Data 15 ianuarie 2014 18:39:23
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

std::ifstream fin("zoo.in");
std::ofstream fout("zoo.out");

const int MAXN = 16100;

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

int n, m;
std::vector<int> aint[3 * MAXN + 100], bridge[3 * MAXN + 100][2];
std::pair<int, int> points[MAXN];
std::vector<int> a;

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

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

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

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

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

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

    build_my_vector(nod, stanga, dreapta);

   /* std::cerr << st << " " << dr << ":\n";
    For (i, 0, aint[nod].size() - 1)
        std::cerr << aint[nod][i] << " ";
    std::cerr << "\n";
    For (i, 0, bridge[nod][0].size() - 1)
        std::cerr << bridge[nod][0][i] << " ";
    std::cerr << "\n";
    */

}

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

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

    int mid = (st + dr) / 2, rez = 0;
    int stanga = nod * 2;
    int dreapta = nod * 2 + 1;

    int lefty = bridge[nod][0][pozr];
    int righty = bridge[nod][1][pozr];

    if (lefty >= aint[stanga].size() || aint[stanga][lefty] > aint[nod][pozr])
        --lefty;
    if (righty >= aint[dreapta].size() || aint[dreapta][righty] > aint[nod][pozr])
        --righty;

    if (l <= mid) rez += query_aint(stanga, st, mid, l, r, bridge[nod][0][pozl], lefty);
    if (r > mid) rez += query_aint(dreapta, mid + 1, dr, l, r, bridge[nod][1][pozl], righty);

    return rez;
}

int query(int x1, int y1, int x2, int y2) {
    int px1 = lower_bound(a.begin(), a.end(), x1) - a.begin() + 1; //arborele este indexat de la 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;

    return query_aint(1, 1, n, px1, px2, py1, py2);
}


int main() {
    fin >> n;

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

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

    build(1, 1, n);

    fin >> m;

    For(i, 1, m) {
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        //fout << query(x1, y1, x2, y2) << "\n";
    }

    return 0;
}