Cod sursa(job #2501360)

Utilizator bogdi1bogdan bancuta bogdi1 Data 29 noiembrie 2019 16:29:10
Problema Zoo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.47 kb
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int INF = 1000000000;
vector<int> arbint[864005];
map<int,int> mp;
vector<int> puncte[216005];
struct Oite
{
    int x,y;
} oi[16005];
struct Drept
{
    int x1,y1,x2,y2;
} que[100005];
int nn;
int bsf(int ind, int val)
{
    int st=0,dr=arbint[ind].size()-1,med,last=INF;
    while(st<=dr){
        med=(st+dr)/2;
        if(arbint[ind][med]>=val){
            last=med;
            dr=med-1;
        }
        else
            st=med+1;
    }
    return last;
}
int bsl(int ind, int val)
{
    int st=0,dr=arbint[ind].size()-1,med,last=-INF;
    while(st<=dr){
        med=(st+dr)/2;
        if(arbint[ind][med]<=val){
            st=med+1;
            last=med;
        }
        else
            dr=med-1;
    }
    return last;
}
void create(int nod, int value)
{
    for(int i=0; i<puncte[value].size(); i++)
        arbint[nod].push_back(puncte[value][i]);
}
void join(int nod, int left, int right)
{
    int i=0,j=0;
    while(i<arbint[left].size() && j<arbint[right].size()){
        if(arbint[left][i]<arbint[right][j]){
            arbint[nod].push_back(arbint[left][i]);
            i++;
        }
        else{
            arbint[nod].push_back(arbint[right][j]);
            j++;
        }
    }
    while(i<arbint[left].size()){
        arbint[nod].push_back(arbint[left][i]);
        i++;
    }
    while(j<arbint[right].size()){
        arbint[nod].push_back(arbint[right][j]);
        j++;
    }
}
void build(int nod, int st, int dr)
{
    if(st==dr)
        create(nod, st);
    else{
        int mij=(st+dr)/2;
        build(2*nod, st, mij);
        build(2*nod+1, mij+1, dr);
        join(nod, 2*nod, 2*nod+1);
    }
}
void build()
{
    build(1, 1, nn);
}
int query(int nod, int st, int dr, int left, int right, int ymin, int ymax)
{
    if(st==left && dr==right){
        int x=bsf(nod, ymin);
        int y=bsl(nod, ymax);
        return max(0, y-x+1);
    }
    else{
        int mij=(st+dr)/2;
        if(right<=mij)
            return query(2*nod, st, mij, left, right, ymin, ymax);
        else{
            if(mij<left)
                return query(2*nod+1, mij+1, dr, left, right, ymin, ymax);
            else
                return query(2*nod, st, mij, left, mij, ymin, ymax)+query(2*nod+1, mij+1, dr, mij+1, right, ymin, ymax);
        }
    }
}
int query(int left, int right, int ymin, int ymax)
{
    return query(1, 1, nn, left, right, ymin, ymax);
}
int main()
{   freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    int n,m,i;
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d%d", &oi[i].x, &oi[i].y);
        mp[oi[i].x];
    }
    scanf("%d", &m);
    for(i=1; i<=m; i++){
        scanf("%d%d%d%d", &que[i].x1, &que[i].y1, &que[i].x2, &que[i].y2);
        mp[que[i].x1];
        mp[que[i].x2];
    }
    map<int, int>::iterator it;
    map<int,int>::iterator it1;
    for(it=mp.begin(), i=1; it!=mp.end(); it++,i++)
        it->second=i;
    nn=i-1;
    for(i=1; i<=n; i++){
        it=mp.find(oi[i].x);
        puncte[it->second].push_back(oi[i].y);
    }
    for(i=1; i<=nn; i++)
        sort(puncte[i].begin(), puncte[i].end());
    build();
    for(i=1; i<=m; i++){
        it=mp.find(que[i].x1);
        it1=mp.find(que[i].x2);
        printf("%d\n", query(it->second, it1->second, que[i].y1, que[i].y2));
    }
    return 0;
}