Cod sursa(job #3163416)

Utilizator Robert_NicuNicu Robert Cristian Robert_Nicu Data 31 octombrie 2023 13:47:12
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <bits/stdc++.h>
#define DIMN 16001
#define DIMM 100001
using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

struct coord{
    int x;
    int y;
}p[DIMN];
struct dreptunghi{
    int x1;
    int x2;
    int y1;
    int y2;
}d[DIMM];

int i, j, len, n, m, poz, ans;
int s[DIMM*5];
vector <int> arb[4*(DIMM+DIMN)];

bool comp(coord x, coord y){
    return (x.x<y.y);
}

int cb(int x){
    int st=0, dr=len-1;
    while(st<=dr){
        int mij=(st+dr)/2;
        if(x==s[mij])
            return mij;
        else
            if(x<s[mij])
                dr=mij-1;
            else st=mij+1;
    }
}

int cbst(int x, int nod){
    int st=0, dr=arb[nod].size()-1;
    while(st<=dr){
        int mij=(st+dr)/2;
            if(x<=arb[nod][mij])
                dr=mij-1;
            else st=mij+1;

    }
    return st;
}

int cbdr(int x, int nod){
    int st=0, dr=arb[nod].size()-1;
    while(st<=dr){
        int mij=(st+dr)/2;
            if(x>=arb[nod][mij])
                st=mij+1;
            else dr=mij-1;

    }
    return dr;
}

void build(int nod, int st, int dr){
    for(i=st; i<=dr; i++)
        arb[nod].push_back(p[i].y);
    sort(arb[nod].begin(), arb[nod].end());
    if(st<dr){
        int mij=(st+dr)/2;
        build(nod*2, st, mij);
        build(nod*2+1, mij+1, dr);
    }
}

void query(int nod, int st, int dr, int q){
    if(st>dr)
        return;
    if(d[q].x1<=p[st].x && p[dr].x<=d[q].x2){
        ans+=(cbdr(d[q].y2, nod)-cbst(d[q].y1, nod)+1);
    }else{
        if(st==dr)
            return;
        int mij=(st+dr)/2;
        if(d[q].x1<=p[mij].x)
            query(nod*2, st, mij, q);
        if(d[q].x2>=p[mij+1].x)
            query(nod*2+1, mij+1, dr, q);
    }
}

int main(){
    fin >> n;
    for(i=1; i<=n; i++){
        fin>>p[i].x>>p[i].y;
        s[len++]=p[i].x;
        s[len++]=p[i].y;
    }
    fin>>m;
    for(i=1; i<=m; i++){
        fin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2;
        s[len++]=d[i].x1;
        s[len++]=d[i].y1;
        s[len++]=d[i].x2;
        s[len++]=d[i].y2;
    }

    sort(s, s+len);

    for(i=1; i<len; i++)
        if(s[i]!=s[poz])
            s[++poz]=s[i];
    len=poz+1;

    for(i=1; i<=n; i++){
        p[i].x=cb(p[i].x);
        p[i].y=cb(p[i].y);
    }
    for(i=1; i<=m; i++){
        d[i].x1=cb(d[i].x1);
        d[i].y1=cb(d[i].y1);
        d[i].x2=cb(d[i].x2);
        d[i].y2=cb(d[i].y2);
    }
    sort(p+1, p+n+1, comp);

    build(1, 1, n);

    for(i=1; i<=m; i++){
        ans=0;
        query(1, 1, n, i);
        fout<<ans<<"\n";
    }
}