Cod sursa(job #3163506)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 31 octombrie 2023 15:39:27
Problema Zoo Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <cmath>
#include <vector>

#define DIM 16000
using namespace std;

//ifstream f("in.in");
//ofstream g("out.out");

ifstream f("zoo.in");
ofstream g("zoo.out");

struct info{
    int x,y;
};

bool cmp(info a,info b){
    return a.x<b.x;
}

info v[DIM+5];
int n,m,X1,X2,Y1,Y2;

vector<int> a[4*DIM+5];

void build(int nod,int st,int dr){

    if(st == dr){
        a[nod].push_back(v[dr].y);

        //cout<<st<<"-"<<dr<<": "<<v[dr].y<<"\n";

        return;
    }

    int mid = (st+dr)/2;

    build(2*nod,st,mid);
    build(2*nod+1,mid+1,dr);

    int i=0,j=0,x,y;

    x = a[2*nod].size();
    y = a[2*nod+1].size();

    while(i<x && j<y){
        if(a[2*nod][i]<a[2*nod+1][j]){
            a[nod].push_back(a[2*nod][i]);
            i++;
        }else{
            a[nod].push_back(a[2*nod+1][j]);
            j++;
        }
    }
    while(i<x){
        a[nod].push_back(a[2*nod][i]);
        i++;
    }
    while(j<y){
        a[nod].push_back(a[2*nod+1][j]);
        j++;
    }

    /*cout<<st<<"-"<<dr<<": ";
    for(int i=0;i<a[nod].size();i++){
        cout<<a[nod][i]<<" ";
    }cout<<"\n";*/

}

int findFirst(int nod,int x){
    int st=0,dr=a[nod].size()-1,sol = 0;
    while(st<=dr){
        int mid = (st+dr)/2;
        if(x<=a[nod][mid]){
            sol = mid;
            dr = mid-1;
        }else{
            st = mid+1;
        }
    }
    return sol;
}

int findLast(int nod,int x){
    int st=0,dr=a[nod].size()-1,sol = 0;
    while(st<=dr){
        int mid = (st+dr)/2;
        if(a[nod][mid]<=x){
            sol = mid;
            st = mid+1;
        }else{
            dr = mid-1;
        }
    }
    return sol;
}


int sol = 0;
void query(int nod,int st,int dr){

    if(v[st].x < X1 || X2 < v[dr].x){
        return;
    }

    if(X1<=v[st].x && v[dr].x<=X2){

        if(a[nod][0] < Y1 || Y2 < a[nod][a[nod].size()]-1)
            return;

        sol += (findLast(nod,Y2) - findFirst(nod,Y1)+1);

        return;
    }

    if(st == dr){
        return;
    }

    int mid = (st+dr)/2;

    if(X1<=v[mid].x){
        query(2*nod,st,mid);
    }
    if(v[mid+1].x <= X2){
        query(2*nod+1,mid+1,dr);
    }
}


int main()
{

    f>>n;
    for(int i=1;i<=n;i++){
        f>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,cmp);

    build(1,1,n);

    f>>m;
    for(int i=1;i<=m;i++){
        f>>X1>>Y1>>X2>>Y2;

        sol=0;
        query(1,1,n);
        g<<sol<<'\n';
    }

    return 0;
}