Cod sursa(job #1335584)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 5 februarie 2015 18:39:56
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define NMAX 16007
#define x first
#define y second

using namespace std;

pair < int, int > a[NMAX];
vector < int > Arbi[4 * NMAX], X;
int n, m;

void Update(int Nod,int St,int Dr){
    if(St == Dr){
        Arbi[Nod].assign(1, a[St].y);
        return;
    }
    int Med = (St + Dr) >> 1;
    Update(2 * Nod, St, Med);
    Update(2 * Nod + 1, Med + 1, Dr);
    Arbi[Nod].resize(Arbi[2 * Nod].size() + Arbi[2 * Nod + 1].size());
    merge(Arbi[2 * Nod].begin(), Arbi[2 * Nod].end(), Arbi[2 * Nod + 1].begin(), Arbi[2 * Nod + 1].end(), Arbi[Nod].begin());
}

int Query(int Nod, int St, int Dr, int x1, int y1, int x2, int y2){
    if(x1 <= St && Dr <= x2)
        return upper_bound(Arbi[Nod].begin(), Arbi[Nod].end(), y2)- lower_bound(Arbi[Nod].begin(), Arbi[Nod].end(),y1);
    if(St == Dr)
        return 0;
    int Ans = 0, Med = (St + Dr) >> 1;
    if(x1 <= Med)
        Ans += Query(2 * Nod, St, Med, x1, y1, x2, y2);
    if(Med < x2)
        Ans += Query(2 * Nod + 1, Med + 1, Dr, x1, y1, x2, y2);
    return Ans;
}
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", &a[i].x, &a[i].y);
        X.push_back(a[i].x);
    }
    sort(X.begin(), X.end());
    sort(a + 1, a + n + 1);
    scanf("%d", &m);
    Update(1, 1, n);
    for(int i = 1; i <= m; ++i){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        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, y1, x2, y2));
    }
    return 0;
}