Cod sursa(job #3292612)

Utilizator Victor5539Tanase Victor Victor5539 Data 8 aprilie 2025 18:42:30
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#define pb push_back

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


const int MAX=120000;
int n,m,i,XMAX,YMAX,sol;
struct elem{
int x,y;}p[16005];

struct elem2{
int x,y,x2,y2;}q[100005];

set <int> s1,s2;
unordered_map <int,int> f1,f2;
vector <int> pct[MAX+5];

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

    return a.y<b.y;
}

vector <int> A[4*MAX+5];


void build(int nod, int st ,int dr)
{
    if (st==dr)
    {
        for (auto x: pct[st])
            A[nod].pb(x);
    }
    else
    {
        int mij=(st+dr)>>1;

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

        int 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, int st ,int dr ,int x, int y, int semn)
{
    if (1<=st && dr<=x)
    {
        sol+=(upper_bound(A[nod].begin(),A[nod].end(),y)-A[nod].begin())*semn;
    }
    else
    {
        int mij=(st+dr)>>1;

        if (1<=mij)
            query(2*nod,st,mij,x,y,semn);

        if (x>=mij+1)
            query(2*nod+1,mij+1,dr,x,y,semn);
    }
}

void queryrectangle(int x1, int y1, int x2 ,int y2)
{
    sol=0;
    query(1,1,XMAX,x2,y2,1);
    if (y1>1)
    query(1,1,XMAX,x2,y1-1,-1);
    if (x1>1)
    query(1,1,XMAX,x1-1,y2,-1);
    if (x1>1 && y1>1)
    query(1,1,XMAX,x1-1,y1-1,+1);
    fout<<sol<<"\n";
}

int main()
{
    fin>>n;
    for (i=1; i<=n; i++)
    {
        fin>>p[i].x>>p[i].y;
        s1.insert(p[i].x);
        s2.insert(p[i].y);
    }

    fin>>m;

    for (i=1; i<=m; i++)
    {
        fin>>q[i].x>>q[i].y>>q[i].x2>>q[i].y2;
        s1.insert(q[i].x);
        s1.insert(q[i].x2);
        s2.insert(q[i].y);
        s2.insert(q[i].y2);
    }

    for (auto x: s1)
    {
        XMAX++;
        f1[x]=XMAX;
    }

    for (auto x: s2)
    {
        YMAX++;
        f2[x]=YMAX;
    }

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

    for (i=1; i<=n; i++)
        pct[f1[p[i].x]].pb(f2[p[i].y]);

    build(1,1,XMAX);

    for (i=1; i<=m; i++)
        queryrectangle(f1[q[i].x],f2[q[i].y],f1[q[i].x2],f2[q[i].y2]);




    return 0;
}