Cod sursa(job #3303864)

Utilizator Victor5539Tanase Victor Victor5539 Data 18 iulie 2025 16:06:17
Problema Zoo Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.54 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");

const int NMAX=16000;
int q,x1,y1,x2,y2,q_x1,q_y1,q_x2,q_y2;
short n,i,y_size,x_size,cnt,sol;
vector <short> A[4*NMAX+5],p[NMAX+5];
vector <int> x,y;

struct point{
int x,y;
short idx_x,idx_y;}v[NMAX+5];

bool compare(point a, point b)
{
    if (a.x!=b.x)
        return a.x<b.x;

    if (a.y!=b.y)
        return a.y<b.y;
}

bool compare2(point a, point b)
{
    if (a.y!=b.y)
        return a.y<b.y;
}


void build(int nod ,short st ,short dr)
{
    if (st==dr)
    {
        for (auto y: p[st])
            A[nod].pb(y);
    }
    else
    {
        short mij=(st+dr)>>1;
        build(2*nod,st,mij);
        build(2*nod+1,mij+1,dr);

        short i=0,j=0;

        while (i<A[2*nod].size() && j<A[2*nod+1].size())
        {
            if (A[2*nod][i]<A[2*nod+1][j])
            {
                A[nod].pb(A[2*nod][i]);
                i++;
            }
            else
            {
                A[nod].pb(A[2*nod+1][j]);
                j++;
            }
        }

        while (i<A[2*nod].size())
        {
            A[nod].pb(A[2*nod][i]);
            i++;
        }

        while (j<A[2*nod+1].size())
        {
            A[nod].pb(A[2*nod+1][j]);
            j++;
        }
    }
}

void query(int nod, short st , short dr , short a, short b, short y1 ,short y2)
{
    if (a<=st && dr<=b)
        sol+=upper_bound(A[nod].begin(),A[nod].end(),y2)-lower_bound(A[nod].begin(),A[nod].end(),y1);
    else
    {
        int mij=(st+dr)>>1;

        if (a<=mij)
            query(2*nod,st,mij,a,b,y1,y2);

        if (b>mij)
            query(2*nod+1,mij+1,dr,a,b,y1,y2);
    }
}

bool intersect(int a, int b, int c, int d)
{
    if (b<c || d<a)
        return false;

    return true;
}

short search1(int val, vector <int> v)
{
    short st=0,dr=v.size()-1,ans=0,mij;

    while (st<=dr)
    {
        mij=(st+dr)>>1;
        if (v[mij]>=val)
        {
            ans=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }

    return ans+1;
}

short search2(int val, vector <int> v)
{
    short st=0,dr=v.size()-1,ans=0,mij;

    while (st<=dr)
    {
        mij=(st+dr)>>1;
        if (v[mij]<=val)
        {
            ans=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }

    return ans+1;
}

int main()
{
    fin>>n;
    for (i=1; i<=n; i++)
        fin>>v[i].x>>v[i].y;

    v[0].x=v[0].y=-2e9-1;

    sort(v+1,v+n+1,compare2);

    for (i=1; i<=n; i++)
    {
        if (v[i].y!=v[i-1].y)
        {
            y_size++;
            y.pb(v[i].y);
        }

        v[i].idx_y=y_size;
    }

    sort(v+1,v+n+1,compare);

    for (i=1; i<=n; i++)
    {
        if (v[i].x!=v[i-1].x)
        {
            x_size++;
            x.pb(v[i].x);
        }

        p[x_size].pb(v[i].idx_y);
    }

    build(1,1,x_size);

    fin>>q;

    while (q--)
    {
        sol=0;

        fin>>x1>>y1>>x2>>y2;

        if (!intersect(x1,x2,x[0],x[x_size-1]) || !intersect(y1,y2,y[0],y[y_size-1]))
        {
            fout<<0<<'\n';
            continue;
        }

        q_x1=search1(x1,x);
        q_x2=search2(x2,x);
        q_y1=search1(y1,y);
        q_y2=search2(y2,y);

//        query(1,1,x_size,q_x1,q_x2,q_y1,q_y2);

        fout<<sol<<'\n';
    }


    return 0;
}