Cod sursa(job #933200)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 29 martie 2013 18:05:14
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define MAX 16005
#define BMAX 1000000
#define x first
#define y second
#define leftSon (nod << 1)
#define rightSon ((nod << 1) | 1)

using namespace std;

int N, M, poz, val, P, xMin, xMax, yMin, yMax;
char buff[BMAX];
pair<int, int> V[MAX];
vector<int> aInt[MAX << 2];

inline int getInt() {
    int val = 0, semn = 1;
    while((buff[poz] < '0' || buff[poz] > '9') && buff[poz] != '-')
        if(++poz == BMAX) fread(buff, 1, BMAX, stdin), poz = 0;
    if(buff[poz] == '-') semn = -1, poz++;
    if(poz == BMAX) fread(buff, 1, BMAX, stdin), poz = 0;
    while(buff[poz] >= '0' && buff[poz] <= '9') {
        val = val * 10 + buff[poz++] - '0';
        if(poz == BMAX) fread(buff, 1, BMAX, stdin), poz = 0;
    } return semn * val;
}

void Insert(int nod, int L, int R) {
    if(L >= R) {
        aInt[nod].push_back(val);
        return;
    } int mid = (L + R) >> 1;
    if(P <= mid) Insert(leftSon, L, mid);
    else Insert(rightSon, mid + 1, R);
}

void FormTree(int nod, int L, int R) {
    if(L >= R) return;
    int mid = (L + R) >> 1;
    FormTree(leftSon, L, mid);
    FormTree(rightSon, mid + 1, R);
    aInt[nod].resize(aInt[leftSon].size() + aInt[rightSon].size());
    merge(aInt[leftSon].begin(), aInt[leftSon].end(), aInt[rightSon].begin(), aInt[rightSon].end(), aInt[nod].begin());
}

void citire() {
    N = getInt();
    for(int i = 1; i <= N; i++) {
        V[i].x = getInt(), V[i].y = getInt();
    } sort(V + 1, V + N + 1);
    for(int i = 1; i <= N; i++) {
        P = i, val = V[i].y;
        Insert(1, 1, N);
    } FormTree(1, 1, N);
}

inline int Query(int nod, int L, int R) {
    if(xMin <= V[L].x && V[R].x <= xMax) {
        return (upper_bound(aInt[nod].begin(), aInt[nod].end(), yMax) - lower_bound(aInt[nod].begin(), aInt[nod].end(), yMin));
    } if(L >= R) return 0;
    int mid = (L + R) >> 1;
    int ans = 0;
    if(xMin <= V[mid].x) ans += Query(leftSon, L, mid);
    if(V[mid + 1].x <= xMax) ans += Query(rightSon, mid + 1, R);
    return ans;
}

void solve() {
    M = getInt();
    for(int i = 1; i <= M; i++) {
        xMin = getInt(), yMin = getInt(), xMax = getInt(), yMax = getInt();
        printf("%d\n", Query(1, 1, N));
    }
}

int main()
{
    freopen("zoo.in", "r", stdin); freopen("zoo.out", "w", stdout);
    fread(buff, 1, BMAX, stdin);
    citire();
    solve();
    fclose(stdin); fclose(stdout);
    return 0;
}