Cod sursa(job #1000467)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 22 septembrie 2013 22:20:46
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include<stdio.h>
#include<vector>
#include<algorithm>

#define MMAX 200007
#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, Ans[MMAX], n, c[MMAX], m, aib[3 * MMAX], Ap[MMAX];

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

void Norm(){
    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];
}

ZOO pune(int xx, int yy, int ap, int K, int TIP){
    ZOO b;
    b.x = xx;
    b.y = yy;
    b.Tip = TIP;
    b.PN = ap;
    b.Ind = K;
    return b;
}

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 xx, yy;
        scanf("%d %d", &xx, &yy);
        a.push_back(pune(xx, yy, 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(pune(x2    , y2    , 1, i, 1));
        a.push_back(pune(x2    , y1 - 1, 0, i, 1));
        a.push_back(pune(x1 - 1, y1 - 1, 1, i, 1));
        a.push_back(pune(x1 - 1, y2    , 0, i, 1));
    }
    Norm();
    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;
}