Cod sursa(job #3162945)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 30 octombrie 2023 10:59:23
Problema Zoo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
ifstream cin("zoo.in");
ofstream cout("zoo.out");
int n,m,s[500050],k,i,last,sol;
pair<int, int>p[16010];
vector<int> A[500050];
struct coord_dreptunghiuri{
    int x1,y1,x2,y2;
}d[100010];
int cauta(int x){
    int st=0,dr=k-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(s[mid]==x)
            return mid;
        else
            if(s[mid]<x)
               st=mid+1;
            else
                dr=mid-1;
    }
}
void build(int nod,int st,int dr){
    for(int i=st;i<=dr;i++)
        A[nod].push_back(p[i].second);
    sort(A[nod].begin(),A[nod].end());
    if(st<dr)
    {
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
    }
}
int cauta_primul(int y,int nod){
    int st=0;
    int dr=A[nod].size()-1;
    while(st <= dr)
    {
        int mid=(st+dr)/2;
        if(A[nod][mid]>=y)
            dr=mid-1;
        else
            st=mid+1;
    }
    return st;
}
int cauta_ultimul(int y,int nod){
    int st=0;
    int dr=A[nod].size()-1;
    while(st <= dr)
    {
        int mid =(st+dr)/2;
        if(A[nod][mid]<=y)
            st=mid+1;
        else
            dr=mid-1;
    }
    return dr;
}
void query(int nod,int st,int dr,int poz){
    if(st>dr)
        return;
    if(d[poz].x1<=p[st].first&&d[poz].x2>=p[dr].first)
        sol+=(cauta_ultimul(d[poz].y2, nod)-cauta_primul(d[poz].y1, nod)+1);
    else
    {
        if(st==dr)
            return;
        int mid=(st+dr)/2;
        if (d[poz].x1<=p[mid].first)
            query(2*nod,st,mid,poz);
        if (d[poz].x2>=p[mid+1].first)
            query(2*nod+1,mid+1,dr,poz);
    }
}
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>p[i].first>>p[i].second;
        s[++k]=p[i].first;
        s[++k]=p[i].second;
    }
    cin>>m;
    for(i=1;i<=m;i++)
    {
        cin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2;
        s[k++]=d[i].x1;
        s[k++]=d[i].y1;
        s[k++]=d[i].x2;
        s[k++]=d[i].y2;
    }
    ///sortam vectorul s si eliminam dublurile
    sort(s,s+k);
    for(i=1;i<k;i++)
    {
        if(s[i]!=s[last])
            s[++last]=s[i];
    }
    k=last+1;
    ///incepem normalizarea
    for(i=1;i<=n;i++)
    {
        p[i].first=cauta(p[i].first);
        p[i].second=cauta(p[i].second);
    }
    for(i=1;i<=m;i++)
    {
        d[i].x1=cauta(d[i].x1);
        d[i].y1=cauta(d[i].y1);
        d[i].x2=cauta(d[i].x2);
        d[i].y2=cauta(d[i].y2);
    }
    sort(p+1,p+n+1);
    build(1,1,n);
    for(i=1;i<=m;i++)
    {
        sol=0;
        query(1,1,n,i);
        cout<<sol<<'\n';
    }
    return 0;
}