Cod sursa(job #1897752)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 1 martie 2017 17:51:00
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <bits/stdc++.h>

using namespace std;

struct pct{
    int x,y;
}point[16005];

bool comp(pct a, pct b){
    return a.x < b.x;
}

int qlf, qrg, qy1, qy2;
vector <int> aint[4 * 16005];

bool compY(pct a, pct b){
    return a.y < b.y;
}

struct compP{
    bool operator ()(pct const& a, int const& b)const{
        return a.x < b;
    }
};

void build(int pos, int lf, int rg){
    if(lf == rg){
        aint[pos].push_back(point[lf].y);
        return;
    }
    int md = (lf + rg)/2;
    build(2 * pos, lf, md);
    build(2 * pos + 1, md + 1, rg);
    merge(aint[2 * pos].begin(), aint[2 * pos].end(), aint[2 * pos + 1].begin(), aint[2 * pos + 1].end(), back_inserter(aint[pos]));
}

int query(int pos, int lf, int rg){
    if(rg < qlf || lf > qrg){
        return 0;
    }
    if(qlf <= lf && rg <= qrg){
        return upper_bound(aint[pos].begin(), aint[pos].end(), qy2) - lower_bound(aint[pos].begin(), aint[pos].end(), qy1);
    }
    int md = (lf + rg)/2;
    return query(2 * pos, lf, md) + query(2 * pos + 1, md + 1, rg);
}

int main()
{
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    int n,q,i,x1,x2;
    scanf("%d", &n);
    for(i = 1;i <= n;i++){
        scanf("%d %d", &point[i].x, &point[i].y);
    }
    sort(point + 1, point + n + 1, comp);
    build(1, 1, n);
    scanf("%d", &q);
    for(i = 1;i <= q;i++){
        scanf("%d %d %d %d", &x1, &qy1, &x2, &qy2);
        pct t;
        t.x = x1;
        qlf = lower_bound(point + 1, point + n + 1, t, [](const pct &a, const pct &b){return a.x < b.x;}) - point;
        t.x = x2;
        qrg = upper_bound(point + 1, point + n + 1, t, [](const pct &a, const pct &b){return a.x < b.x;}) - point - 1;
        printf("%d\n", query(1, 1, n));
    }
    return 0;
}