Cod sursa(job #1099093)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 5 februarie 2014 15:54:10
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <vector>
#include <algorithm>

#include <cstdio>
using namespace std;

const int MAX_N = 16002;

int N, M;
vector < int > A[3 * MAX_N], temp;
pair < int, int > v[MAX_N];

void update(int node, int st, int dr, int x, int val) {
    if(st == dr)
        A[node].push_back(val);
    else {
        int ls = 2 * node, rs = 2 * node + 1, m = (st + dr) / 2;

        if(x <= m)
            update(ls, st, m, x, val);
        else update(rs, m + 1, dr, x, val);

        A[node].push_back(val);
    }
}

int query(int node, int st, int dr, int x, int y, int val1, int val2) {
    if(x > y)
        return 0;
    if(x <= st && dr <= y)
        return upper_bound(A[node].begin(), A[node].end(), val2) - lower_bound(A[node].begin(), A[node].end(), val1);
    else {
        int ls = 2 * node, rs = 2 * node + 1, m = (st + dr) / 2, ret = 0;

        if(x <= m)
            ret += query(ls, st, m, x, y, val1, val2);
        if(y > m)
            ret += query(rs, m + 1, dr, x, y, val1, val2);

        return ret;
    }
}

int main() {
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);

    scanf("%d", &N);
    for(int i = 1; i <= N; ++i)
        scanf("%d %d", &v[i].first, &v[i].second);

    vector < int > temp2;
    for(int i = 1; i <= N; ++i)
        temp2.push_back(v[i].first);

    sort(temp2.begin(), temp2.end());
    temp.push_back(-2000000001);
    temp.push_back(temp2[0]);
    for(size_t i = 1; i < temp2.size(); ++i)
        if(temp2[i] != temp2[i - 1])
            temp.push_back(temp2[i]);


    for(int i = 1; i <= N; ++i) {
        v[i].first = lower_bound(temp.begin(), temp.end(), v[i].first) - temp.begin();
        swap(v[i].first, v[i].second);
    }
    sort(v + 1, v + N + 1);

    for(int i = 1; i <= N; ++i)
        update(1, 1, N, v[i].second, v[i].first);

    scanf("%d", &M);
    for(int i = 1, X1, Y1, X2, Y2; i <= M; ++i) {
        scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2);

        int x = 0;
        for(int l = 0, r = temp.size() - 1, m; l <= r; ) {
            m = (l + r) / 2;
            if(temp[m] >= X1)
                x = m, r = m - 1;
            else l = m + 1;
        }
        X1 = x;

        x = temp.size() - 1;
        for(int l = 0, r = temp.size() - 1, m; l <= r; ) {
            m = (l + r) / 2;
            if(temp[m] > X2)
                r = m - 1;
            else x = m, l = m + 1;
        }
        X2 = x;

        printf("%d\n", query(1, 1, N, X1, X2, Y1, Y2));
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}