Cod sursa(job #1141188)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 12 martie 2014 18:14:51
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define NMAX 300007
#define FORIT(it, v) for(vector<int>::iterator it = (v).begin(); it != (v).end(); ++it)
#define FORITZ(it, v) for(vector<zoo>::iterator it = (v).begin(); it != (v).end(); ++it)

using namespace std;

struct zoo{
    int x;
    int y;
    bool Tip;
    bool PN;
    int Ind;
};

vector< zoo > a;
int N, n, c[NMAX], m, Aib[3 * NMAX], Ap[NMAX], Ans[NMAX];

zoo make_zoo(int _x, int _y, int ap, int K, int Tip){
    zoo b;
    b.x = _x;
    b.y = _y;
    b.Tip = Tip;
    b.PN = ap;
    b.Ind = K;
    return b;
}

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

void Normalizare(){
    vector<int> v;
    for(int i = 0; i < a.size(); ++i)
        v.push_back(a[i].y);
    vector<int> u = v;
    sort(u.begin(), u.end());
    u.resize(unique(u.begin(), u.end()) - u.begin());
    FORIT(it, v){
        *it = lower_bound(u.begin(), u.end(), *it) - u.begin() + 1;
        N = max(N, *it);
    }
    for(int i = 0; i < a.size(); ++i)
        a[i].y = v[i];
    v.clear();
    u.clear();
    for(int i = 0; i < a.size(); ++i){
        v.push_back(a[i].x);
        u.push_back(a[i].x);
    }
    sort(u.begin(), u.end());
    u.resize(unique(u.begin(), u.end()) - u.begin());
    FORIT(it, v){
        *it = lower_bound(u.begin(), u.end(), *it) - u.begin() + 1;
    }
    for(int i = 0; i < a.size(); ++i)
        a[i].x = v[i];
}

void update(int poz, int val, int N){
    while (poz <= N){
        Aib[poz] += val;
        poz += poz & (poz ^ (poz - 1));
    }
}

int query(int poz){
    int sol = 0;
    while (poz){
        sol += Aib[poz];
        poz -= poz & (poz ^ (poz - 1));
    }
    return sol;
}

int main(){
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        int _x, _y;
        scanf("%d %d", &_x, &_y);
        a.push_back(make_zoo(_x, _y, 0, 0, 0));
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i){
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        a.push_back(make_zoo(x2, y2, 1, i, 1));
        a.push_back(make_zoo(x2, y1 - 1, 0, i, 1));
        a.push_back(make_zoo(x1 - 1, y1 - 1, 1, i, 1));
        a.push_back(make_zoo(x1 - 1, y2, 0, i, 1));
    }
    Normalizare();
    sort(a.begin(), a.end(), cmp);
    FORITZ(it, a)
        if(it->Tip == 0)
            update(it->y, 1, N);
        else
            if(it->PN == 0)
                Ans[it->Ind] -= query(it->y);
            else
                Ans[it->Ind] += query(it->y);
    for(int i = 1; i <= m; ++i)
        printf("%d\n", Ans[i]);
    return 0;
}