Cod sursa(job #1237950)

Utilizator smaraldaSmaranda Dinu smaralda Data 5 octombrie 2014 11:47:35
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include<stdio.h>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

#define leftSon 2 * node
#define rightSon 2 * node + 1
#define mid (left + right) / 2
#define ITERATOR vector <int>:: iterator

const int NMAX = 16005;

struct POINT {
    int x, y;

    void read() {
        scanf("%d%d", &x, &y);
    }

    bool operator < (POINT other) const {
        if(x == other.x)
            return y < other.y;
        return x < other.x;
    }
} pts[NMAX];
vector <int> y[NMAX], yAint[NMAX * 4];

void build (int node, int left, int right) {
    if(left == right) {
        yAint[node] = y[left];
        return;
    }

    build(leftSon, left, mid);
    build(rightSon, mid + 1, right);

    yAint[node].resize(yAint[leftSon].size() + yAint[rightSon].size());
    merge(yAint[leftSon].begin(), yAint[leftSon].end(), yAint[rightSon].begin(), yAint[rightSon].end(), yAint[node].begin());
}

int query (int node, int left, int right, int a, int b, int y1, int y2) {
    if(right < left)
        return 0;
    if(left >= a && right <= b) {
        int aux = upper_bound(yAint[node].begin(), yAint[node].end(), y2) - lower_bound(yAint[node].begin(), yAint[node].end(), y1);
        if(aux > 0)
            return aux;
        return 0;
    }

    int val1, val2;
    val1 = val2 = 0;

    if(a <= mid)
        val1 = query(leftSon, left, mid, a, b, y1, y2);
    if(b > mid)
        val2 = query(rightSon, mid + 1, right, a, b, y1, y2);

    return val1 + val2;
}

int main() {
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out" ,"w", stdout);
    int i, n, m, x1, x2, y1, y2, res;
    ITERATOR lowerbound, upperbound;

    vector <int> x;

    scanf("%d", &n);
    for(i = 1; i <= n; ++ i)
        pts[i].read();
    sort(pts + 1, pts + 1 + n);

    for(i = 1; i <= n; ++ i) {
        y[i].push_back(pts[i].y);
        x.push_back(pts[i].x);
    }

    build(1, 1, n);

    sort(x.begin(), x.end());
    /*scanf("%d", &m);
    for(i = 1; i <= m; ++ i) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

        lowerbound = lower_bound(x.begin(), x.end(), x1);
        upperbound = upper_bound(x.begin(), x.end(), x2);

        x1 = lower_bound(x.begin(), x.end(), x1) - x.begin() + 1;
        x2 = upper_bound(x.begin(), x.end(), x2) - x.begin();

        printf("%d\n", query(1, 1, n, x1, x2, y1, y2));
    }*/
    return 0;
}