Cod sursa(job #749958)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 19 mai 2012 19:24:13
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

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

struct pct {
    int x, y;
};

const int N = 16110;

int n, m, x1, val1, x2, val2, x, y, rez;
pct v[N];
vector<int> aint[4*N];

inline bool cmp(const pct &a, const pct &b) {
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

inline int min(const int &a, const int &b) {
    return a < b ? a : b;
}

void build(const int &nod, const int &pozx, const int &pozy) {
    if(pozx == pozy) {
        aint[nod].push_back(v[pozx].y);
        return;
    }

    int mid = (pozx + pozy)>>1;

    build(2*nod, pozx, mid);
    build(2*nod + 1, mid + 1, pozy);

    aint[nod].resize(aint[2*nod].size() + aint[2*nod + 1].size());
    merge(aint[2*nod].begin(), aint[2*nod].end(), aint[2*nod + 1].begin(), aint[2*nod + 1].end(), aint[nod].begin());
}

void query(const int &nod, const int &pozx, const int &pozy) {

    if(pozx>=x && pozy<=y) {
        rez += lower_bound(aint[nod].begin(), aint[nod].end(), val2 + 1) - lower_bound(aint[nod].begin(), aint[nod].end(), val1);

        return;
    }

    int mid = (pozx + pozy)>>1;

    if(mid >= x)
        query(2*nod, pozx, mid);
    if(mid < y)
        query(2*nod + 1, mid + 1, pozy);

}

char buff[101];
int p;

inline int ter() {
    int t = 0, ver = 0;

    if(buff[p] == '-') {
        ver = 1;
        ++p;
    }

    while(buff[p] >= '0' && buff[p] <= '9')
        t = t * 10 + buff[p++] - '0';
    ++p;
    return ver ? -t : t;
}

int main() {
    int i, j, pas;

    in >> n;

    for(i = 1; i<=n; ++i)
        in >> v[i].x >> v[i].y;

    sort(v + 1, v + n + 1, cmp);

    build(1, 1, n);

    in >> m;
    in.get();

    for(i = 1; i<=m; ++i) {
        in.getline(buff, 100); p =0;
        x1 = ter();
        val1 = ter();
        x2 = ter();
        val2 = ter();

        pas = 1<<13;
        for(j = 0; pas; pas>>=1)
            if(j + pas <= n && v[j + pas].x < x1)
                j += pas;
        x = j + 1;

        pas = 1<<13;
        for(j = 0; pas; pas>>=1)
            if(j + pas <= n && v[j + pas].x <= x2)
                j += pas;
        y = j;

        rez = 0;

        query(1, 1, n);

        out << rez << "\n";
    }

    return 0;
}